+**********************************************************************
*
*
*                          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