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.