The Graph Isomorphism Problem

Invited Talk by Martin Fürer

The graph isomorphism problem resists classification in terms of computational complexity. There is strong evidence that it is not NP-complete, yet nobody seems to have even an idea for a polynomial time algorithm, and indeed none might exist. Still much progress has been made over the last thirty years. The subclasses of graphs with bounded genus, bounded eigenvalue multiplicity, and bounded degree have all been shown to be testable in polynomial time. The methods come from combinatorics, the theory of finite groups, linear algebra, and mathematical logic.

The most natural combinatorial method for the graph isomorphism problem is the k-dimensional Weisfeiler-Lehman method. The aim is to classify the k-tuples of vertices by their neighborhoods in order to obtain a classification of the vertices themselves. An initial hope to obtain all known polynomial time isomorphism test results based on the k-dimensional Weisfeiler-Lehman method has been shown to fail. There are some interesting classes of graphs on which this method is amazingly ineffective in two ways. Most importantly, sometimes k has to be of order n to succeed. Furthermore, when the method succeeds for a constant k, it is possible that a large (even though polynomial) number of iterations is required. On the other hand, the k-dimensional Weisfeiler-Lehman method is successful for graphs of bounded genus.

There are many long standing open problems. The question whether Graph Isomorphism is in P is the most obvious one. Could one at least improve the old upper bound for general graph isomorphism based on Zemlyachenko's method? For more than twenty years, this bound has been moderately exponential, with the square root of the number of vertices in the exponent. It would still be interesting to better understand the power of the combinatorial method in general and the k-dimensional Weisfeiler-Lehman method in particular. The latter has strong connections to games and the expressive power of certain restricted logics.