Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is there an algorithm which will allow me to find an isomorphism between two graphs if I have their adjacency lists?

share|improve this question
1  
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: en.wikipedia.org/wiki/Graph_isomorphism_problem –  joriki Mar 30 '11 at 11:44
add comment

2 Answers

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.

share|improve this answer
    
Even more than that, the graph isomorphism problem is still not even know to be P-complete (even though it most likely is). –  Mitch Mar 30 '11 at 16:36
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.