Logic and
Theory of
Discrete Systems

Informatik 7

The Graph Isomorphism Problem

Martin Grohe, Pascal Schweitzer, Erkal Selman, Sandra Kiefer

The question of whether there is a polynomial time algorithm deciding if two graphs are isomorphic has been one of the best-known open problems in theoretical computer science for more than forty years. Indeed, the graph isomorphism problem is one of the very few natural problems in NP that is neither known to be in P nor known to be NP-complete. The question is still wide open, but a number of deep partial results giving polynomial time algorithms for specific classes of graphs are known. Many of them have been obtained through a group theoretic approach that dominated the research on the graph isomorphism problem since the early 1980s.

In this project, we explore new approaches to the graph isomorphism problem that are based on structural graph theory and on connections between logical definability and certain combinatorial and linear programming algorithms for isomorphism testing. Our focus in the last year was on the following two topics.

Combinatorial Algorithms and Mathematical Programming Approaches.

A simple and efficient, yet extremely important algorithm for isomorphism testing is the colour refinement algorithm. We analysed the running time of colour refinement in detail. Despite the fact that the algorithm has been used as a subroutine in most practical isomorphism tools for more than thirty years, there were still missing pieces in the analysis. We established a quasilinear upper bound even for the canonical version of the algorithm and a matching lower bound that applies to a wide class of algorithms.

It is known that there is a precise correspondence between the colour refinement and a natural linear programming approach to the graph isomorphism problem. E. Selman gave new elementary proof of this correspondence that is arguably much simpler than those known before. We currently study variations of the linear programming approach using semidefinite programming techniques and systems of linear equations over finite fields or integral domains. There is a “higher dimensional” generalisation of the colour refinement algorithm, which is known as Weisfeiler-Lehman algorithm. The higher dimensional version also has a natural linear programming characterisation, and there are also interesting variations. All these techniques give new polynomial time algorithms. Our goal is to understand the power of these algorithms.

Graph Isomorphism Testing on Restricted Graph Classes.

Much of the research on the graph isomorphism problem over the last 40 years was concerned with the design of polynomial time isomorphism tests for specific graph classes. One of the most general results in this direction, due to Grohe and Marx, gives polynomial time isomorphism tests for all graph classes that exclude some fixed graph as a topological subgraph. In the last year, we looked at a smaller family of graph classes, classes of graphs that can be embedded in a fixed surface, but tried to find more efficient than just polynomial time algorithms. We looked into two directions, one is fixed-parameter tractability and the other logarithmic space, and obtained promising partial results for both.

Funding: DFG