Is there an algorithm which will allow me to find an isomorphism between two graphs if I have their adjacency lists?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
As requested, my comment as an answer:
The graph isomorphism problem is unusual in that it is NP but probably not NP-complete and no polynomial-time algorithm is known. The Wikipedia article has references for some state-of-the-art algorithms.
There is the naive algorithm which tries all permutations of the vertices of 1 graph to map to the other, and then for each permutation, checks if the mapping is an isomorphism. There are $V!$ permutations and checking the mapping takes $O(V+E)$ (why?). So the runtime is exponential.
There are theoretical algorithms that are sub-exponential but super-polynomial and use pretty etherial assumptions (the classification of finite simple groups).
For actual practical efficient software that decides isomorphism, see Brendan McKay's nauty software. As usual, software for hard problems usually turn out to be pretty fast on most instances, because of convenient optimizations employed, and, if the algorithm is adaptive enough, most examples really are pretty easy. (the above naive algorithm is not adaptive at all, you have to go through all permutations to be sure.)