What is the significance of the graph isomorphism problem?

Question

It seems that graph isomorphism is an overwhelmingly interesting problem, particularly computationally. Why is that? What are the (theoretical and practical) implication of the existence of an algorithm, which decides isomorphism of graphs effectively? (I have assumed that there is still no such algorithm known to human, am I right?)

Answer 1

You are mistaken that there is no known algorithm for graph isomorphism. There is an obvious algorithm: given graphs $G$ and $H$ with the same number of vertices, enumerate all possible bijective mappings from the vertices of $G$ to the vertices of $H$, and then check (in $O(v^2)$ time) to see if each mapping is an isomorphism. This algorithm is guaranteed to terminate; it has running time $O(v!v^2)$.

As I understand it, though, the theoretical significance of this problem is that it is suspected to be NP-intermediate (NPI). That is:

1. It is clearly in NP. (The NTM guesses a possible isomorphism and then checks it in polynomial time)
2. It is suspected not to be NP-complete
3. It is suspected not to be in P.

The existence of an NPI problem is equivalent to P≠NP, so NPI problems are interesting for at least this reason.

Garey and Johnson give the following reasons for suspecting that graph isomorphism might be NPI:

Researchers who have attempted to prove that GRAPH ISOMORPHISM is NP-complete have noted that its nature is much more constrained than that of a typical NP-complete problem, such as SUBGRAPH ISOMORPHISM. NP-completeness proofs seem to require a bit of leeway; if the desired structure $X$ (subset, permutation, schedule, etc.) exists, it should still exist even if certain aspects of the instance are locally altered. Forexample, a function $f$ will be an isomorphism between a graph $H$ and a subgraph of a graph $G$ even if we add edges to $G$ or delete edges not in the image of $f$. However, if $f$ is an isomorphism between $H$ and $G$ itself, then any change in $G$ must be reflected by a corresponding change in $H$, or else $f$ will no longer be an isomorphism. In other words, proofs of NP-completeness seem to require a certain amount of redundancy in the target problem, a redundancy that GRAPH ISOMORPHISM lacks. Unfortunately, this lack of redundancy does not seem to be much of a help in designing a polynomial time algorithm for GRAPH ISOMORPHISM either, so perhaps it belongs to NPI.

(Computers and Intractibility, pages 155–156)

In contrast, the subgraph isomorphism problem is known to be NP-complete. This is the problem of deciding, given graphs $G$ and $H$, whether $G$ is isomorphisc to some subgraph of $H$. An efficient solution to this problem obviously solves Clique, Maximal Independent Set, Hamiltonian Cycle, and other similar problems.