Two graphs which contain the same number of graph vertices connected in the same way are said to be isomorphic. Formally, two graphs and with graph vertices are said to be isomorphic if there is a permutation of such that is in the set of graph edges iff is in the set of graph edges.
(so, now I have two graphs and even I know they are isomorphic. but I don't have an efficient way of finding that permutation to prove they are isomorphic. I just try to find it but it's not a good way because it takes too much time and is like a random permutation.
Is there any algorithm or systematic way of finding the permutation between two isomorphic graphs?
Thanks in advance.
Best Answer
This a very interesting question which I am afraid has (as of the moment) a somewhat disappointing answer.
The problem of graph isomorphism has been an object of study of Computational Complexity since the beginnings of the field. It is clearly a problem belonging to NP, that is, the class of problems for which the answers can be easily verified given a 'witness'- an additional piece of information which validates in some sense the answer.
For example, given two isomorphic graphs a witness of its isomorphism could be the permutation which transforms one graph into the other.
Now for the interesting part. NP is further divided into P (polynomial time solveable) problems, NP-complete problems and NP-intermediate problems. An NP complete problem is one whose solution can be used to encode any other NP problem, meaning that if you could efficiently solve one NP-complete problem, you could efficiently solve all of them, and thus $P=NP$.
However, most researchers believe that $P\ne NP$. One of the consequences of this
is the existence of NP-intermediate problems (Ladner's theorem) - problems which
are in NP but are not in P nor NP-complete. One remarkable aspect of the proof of
Ladner's theorem is that the hypothetical language constructed is very unnatural.
It is an open problem to find an actual NP-intermediate language.
Some contenders have been disqualified as potential candidates for NP-intermediateness, but graph isomorphism is one of the remaining. We do not actually know whether GI is in P, NP-complete or NP-intermediate.
The evidence however suggests that it is either NP-intermediate or in P. There is a very recent advance, due to Babai, which shows that GI is solvable in quasi-polynomial time, which is something we would not expect from a NP-complete problem.
Hope I have not left any major detail out. Feel free to ask questions about GI or its cousin, graph non-isomorphism.