The complexity of Graph Isomorphism (GI) is one of the major open problems. It is easy to see that . It is known that
. The following theorem states that it is unlikely that GI is NP-complete.
Theorem [Schöning’87, BHZ’87] : If GI is NP-complete then the polynomial hierarchy collapses to its second level.
The counting version of GI is known to be reducible to its decisional version. A polynomial time algorithm solving GI would be a major breakthrough. The best known algorithm runs in for graphs with
vertices. Several special cases are shown to be in P. Several problems are known to be GI-hard. See this wikipedia article for details. GI is widely believed to be an NP-intermediate problem.
Conjecture : If
, then GI is neither NP-complete nor in P.
Note that if the above conjecture is true then GI is P-hard. Is GI known to be P-hard ? What is the best known hardness of GI ? Well… we know very little about the hardness of GI. The following exercises show that GI is L-hard.
Exercise : Consider the following restricted automorphism problem: Given a graph
and two lists of nodes
, is there an automorphism in G mapping
to
for 1 ≤ i ≤ k ? Show that this problem is reducible to GI.
Exercise : Show that Undirected ST-connectivity is reducible to the above mentioned automorphism problem.
Torán [Torán’00] proved the following hardness theorem. Informally speaking, GI is hard for all complexity classes defined in terms of the number of accepting computations of a nondeterministic logarithmic space machine. These are the best known hardness results for GI.
Theorem [Torán’00] : GI is hard for
,
,
and
.
All these hardness results are under DLOGTIME uniform many-one reductions.
is the class of problems
Turing reducible to the determinant [Cook’85]. It is known that
and
. Hence the best known hardness of GI is DET-hardness. However, we do not know the exact complexity of
i.e., we don’t know where
lies in terms of the known complexity classes between
and
. In particular, what is the relation between
and
?
Torán also showed a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism. More details about the complexity of perfect matching in a future blog post.
Open Problems:
- Is GI LogCFL-hard ?
- Is DET LogCFL-hard ? What is the relation between LogCFL and DET ? This is an independent long-standing open problem. It deserves a separate blog post.
- Is
? A proof of this would imply that “if GI is NP-complete then
“, improving the above mentioned theorem.
- Is GI in P for strongly regular graphs ? The best known algorithm for strongly regular graphs, given by Spielman [Spielman’96], runs in time
.
References :
- [BHZ’87] R. Boppana, J. Håstad, and S. Zachos , “Does co-NP have short interactive proofs?”, Information Processing Letters 25(2), pages 127-132, (1987).
- [Schöning’87] Uwe Schöning, Graph isomorphism is in the low hierarchy, Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, 1987, 114–124; also: Journal of Computer and System Sciences, vol. 37 (1988), 312–323
- [Cook’85] Stephen A. Cook, A Taxonomy of Problems with Fast Parallel Algorithms Information and Control 64(1-3): 2-21 (1985)
- [Spielman’96] Daniel A. Spielman, Faster isomorphism testing of strongly regular graphs, STOC ’96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, ACM, pp. 576–584
- [Torán’00] Jacobo Torán, On the Hardness of Graph Isomorphism. FOCS’2000, also: SIAM J. Comput. 33(5): 1093-1108 (2004)