TITLE: The graph isomorphism problem
SPEAKER: Jannis Bulian (Computer Lab, The University of Cambridge)

ABSTRACT:

The graph isomorphism problem is the problem of determining, given a pair of graphs G and H, whether they are isomorphic. This problem has an unusual status in complexity theory as it is neither known to be in P nor known to be NP-complete. It is one of the few natural problems for which this is the case.

For a variety of special graph classes there are algorithms that solve the graph isomorphism problem in polynomial time. In recent years this has lead to a more detailed study in the framework of parameterized complexity. Parameterized complexity theory is a two-dimensional approach to the study of the complexity of computational problems. The run-time of an algorithm is not only measured in terms of the size of the input, but also an additional number associated with the input.

A commonly studied means of parameterizing graph problems is the deletion distance from triviality, which counts vertices that need to be deleted from a graph to place it in some class for which efficient algorithms are known. In the context of graph isomorphism, we define triviality to mean a graph with maximum degree bounded by a constant, as such graph classes admit polynomial-time isomorphism tests. We generalise deletion distance to a measure we call elimination distance to triviality, based on elimination trees or tree-depth decompositions. We establish that graph canonisation, and thus graph isomorphism, is FPT when parameterized by elimination distance to bounded degree, generalising results of Bouland et al. on isomorphism parameterized by tree-depth.