The power of algorithmic approaches to the graph isomorphism problem

  • Die Stärke algorithmischer Ansätze für das Graphisomorphieproblem

Neuen, Daniel; Grohe, Martin (Thesis advisor); Schweitzer, Pascal (Thesis advisor); Babai, László (Thesis advisor)

Aachen (2019, 2020)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2019


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 (STOC 2016), 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. Also, the situation has led to a number of algorithms solving the isomorphism problem on restricted classes of input graphs. In this thesis, we continue the investigation of various standard approaches to the Graph Isomorphism Problem to further broaden our understanding on the power and limits of such approaches. In particular, this leads to several improved algorithms solving the isomorphism problem for important restricted classes of graphs. One of the most fundamental methods in the context of graph isomorphism testing is the Weisfeiler-Leman algorithm, which iteratively computes an isomorphism-invariant coloring of vertex-tuples. While the algorithm is unable to decide the isomorphism problem itself, it is commonly used as a subroutine and, for various restricted graph classes, it already serves as a complete isomorphism test. In the latter direction we prove for example that the Weisfeiler-Leman dimension of graph classes of bounded rank-width is bounded. While it was already known that the isomorphism problem for graphs of rank-width at most k is polynomial-time solvable (Grohe and Schweitzer, FOCS 2015), the previous best algorithm is complicated and the exponent of the running time depends non-elementary on k. In contrast, our analysis of the Weisfeiler-Leman algorithm yields a simple isomorphism test running in time n^{O(k)}. A framework closely related to the Weisfeiler-Leman algorithm and which works particularly well in practice is the Individualization-Refinement paradigm. Extending our understanding on the limits of combinatorial approaches we provide the first exponential lower bounds on the worst case complexity of a large and natural class of algorithms within this framework. In particular, this includes all practical state-of-the-art isomorphism tools answering an open question from Babai (STOC 2016) on the worst-case complexity of such solvers. 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's polynomial time algorithm for testing isomorphism of bounded degree graphs (JCSS 1982). Adapting the novel group-theoretic methods by Babai developed for his quasipolynomial time isomorphism test (STOC 2016) we give an isomorphism test for graphs of maximum degree d running in time n^{polylog(d)}. This significantly improves over the previous best isomorphism test for graphs of maximum degree d running in time n^{O(d / log d)} (Babai, Kantor and Luks, FOCS 1983). With Luks's algorithm being used as a subroutine in a number of other algorithms it is natural to ask for the consequences of this improvement. Besides simple applications regarding structures of small degree, we present an isomorphism test for graphs of tree-width k running in time 2^{k polylog(k)} poly(n) improving the fixed-parameter tractable algorithm of Lokshtanov et al. (FOCS 2014) running in time 2^{O(k^{5} log k)} poly(n).