Abstract

Two 90-minute talks will be given, about testing graph isomorphism in quasipolynomial time. These talks are aimed at a general audience, and are distinct from the talk on Thursday in the “Quantum Algorithms” workshop.

One of the fundamental computational problems in the complexity class NP on Karp’s 1973 list, the Graph Isomorphism problem (GI) asks to decide whether or not two given graphs are isomorphic.

While program packages exist that solve this problem remarkably efficiently in practice (McKay, Piperno, and others), for complexity theorists the problem has been notorious for its unresolved asymptotic worst-case complexity: strong theoretical evidence suggests that the problem should not be NP-complete, yet the worst-case complexity has stood at $\exp(O(\sqrt{v\log v}))$ (Luks, 1983) for decades, where $v$ is the number of vertices.

By addressing the bottleneck situation for Luks’s method, we have recently reduced this ``moderately exponential’’ upper bound to quasipolynomial, i.e., $\exp((\log v)^c)$.

We actually solve the more general string isomorphism problem (SI) (``can a given string be transformed into another given string under the action of a given permutation group ?’‘), defined in Luks’s seminal 1980/82 paper (see below) that introduced powerful group theoretic divide-and-conquer methods in the design of SI and GI algorithms.

We attack the bottleneck situation for Luks’s method through local/global interaction. Key role is played by a group theoretic lemma that enables the construction of global automorphisms out of local information. The lemma is used to create ``local certificates’’ of full symmetry or its absence. Subsequently the local certificates are aggregated to a canonically embedded structure which is then exploited to produce a significant reduction of the problem size at moderate multiplicative cost, leading to quasipolynomial recurrence. This reduction is accomplished via combinatorial partitioning techniques.

The first talk will focus on the core group theoretic method; in the second talk we shall discuss the combinatorial partitioning techniques.

Elements of undergraduate-level group theory will be assumed.

The paper is available at arXiv:1512.03547.

Helpful reading:

E.M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comp. Sys. Sci., 25:42—65, 1982.