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?)
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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:
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:
(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.