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?)


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 isomorphic to some subgraph of $H$. An efficient solution to this problem obviously solves Clique, Maximal Independent Set, Hamiltonian Cycle, and other similar problems.

  • $\begingroup$ Nice answer! Btw. I think the poster meant that there is no known "effective" (which probably means polynomial) algorithm that decides graph isomorphism. Which is true. $\endgroup$ Sep 4 '12 at 4:47
  • 2
    $\begingroup$ @GaborCsardi I wondered that myself. But "effective" is an unusual word to use, and has a precise technical meaning in this context, so I took them at their word. $\endgroup$
    – MJD
    Sep 4 '12 at 10:05
  • $\begingroup$ @MJD: Note that there are some languages where the word for "efficient" is disappointingly close to "effective". For example, "efficient" is effektiv in Danish. $\endgroup$ Sep 4 '12 at 13:44
  • 2
    $\begingroup$ @Henning Okay, but I'm not sure it would be useful for me to try to second-guess the poster's expressed meaning on what they might possibly have meant had it been written in some other language. I think a better strategy might be to take them at their word and then wait to see if they post clarifications in response. $\endgroup$
    – MJD
    Sep 4 '12 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.