+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Dienstag, 17. Dezember 2019, 12.00 Uhr Ort: Raum 5053.2 (großer Bit-Raum), Ahornstr. 55 Referent: Daniel Neuen M.Sc. Lehrstuhl Informatik 7 Thema: The Power of Algorithmic Approaches to the Graph Isomorphism Problem Abstract: The Graph Isomorphism Problem asks, given two input graphs, whether they are structurally the same, that is, whether there is a renaming of the vertices of the first graph in order to transform it to the second graph. By a recent breakthrough result of Babai, this problem can be solved in quasipolynomial time. However, despite extensive research efforts, it remains one of only few natural problems in NP that are neither known to be solvable in polynomial time nor known to be NP-complete. Over the past five decades several powerful techniques tackling the Graph Isomorphism Problem have been investigated uncovering various surprising links between different approaches. One of the most fundamental methods in the context of graph isomorphism testing is the Weisfeiler-Leman algorithm and the related paradigm of individualization and refinement. The latter is in particular employed in all practical tools tackling the isomorphism problem. We present new upper and lower bounds on the power of such purely combinatorial approaches. For example, this leads to the first exponential lower bounds on the worst-case complexity of all state-of-the-art isomorphism tools used in practice. A second crucial approach to the Graph Isomorphism Problem is based on group-theoretic techniques. In this direction, one of the algorithmic cornerstones is Luks polynomial time algorithm for testing isomorphism of bounded degree graphs. Adapting the novel group-theoretic methods by Babai developed for his quasipolynomial time isomorphism test we give an isomorphism test for graphs of maximum degree d with a running time bounded by a polynomial of degree polylogarithmic in d. As a consequence of this result we also obtain an improved fpt algorithm for testing isomorphism of graphs of bounded tree-width. Es laden ein: die Dozentinnen und Dozenten der Informatik