Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
Is there a good algorithm to determine whether two graphs are isomorphic or not ?
Are there any conditions that are sufficient to determine an isomorphism between two graphs?
I've just started studying graph theory and I'm struggling with isomorphisms.
In practice, graph isomorphism can be tested efficiently in many instances by Brendan McKay's NAUTY program. There was a question about the workings of the NAUTY algorithm previously on this site, and one of the comments (by user gilleain) linked to this explanation of McKay's Canonical Graph Labeling Algorithm.
The graph isomorphism problem is suspected to be neither in P nor NP-complete, although it is clearly in NP.
You can look at the bibliography of the linked Wikipedia page for further details and related problems.
There are lots easy of necessary conditions.
If two graphs are isomorphic, they must have the same invariants, e.g., same number of vertices, same number of edges, same degree sequence (up to reordering), same number of components, same diameter (for corresponding components), etc.
In practice, for simple examples, if two graphs are not isomorphic, comparing the standard invariants will produce a "witness against".
However, there is no known finite set of invariants that can be computed in polynomial time (polynomial as a function of the length of the graph specification) which has been shown to suffice to prove isomorphism.
Of course, if you can (sometimes by inspection) produce a bijection that preserves adjacency, then there's your isomorphism!
In trying to find an explicit isomorphism, the point-level invariants help narrow the search.
For example, an isomorphism must map vertices to vertices of the same degree.
Similarly, if a vertex in one graph is in a cycle of a given length, then it must map to a vertex with the same property.
These are examples of "point-level" invariants.
Once again, in practice, for simple examples, if two graphs are isomorphic, considering standard point-level invariants will typically be enough to actually find an isomorphism.
Is there a good algorithm to determine whether two graphs are isomorphic or not
Aside from NAUTY mentioned by Noam in another answer, there's also some more modern algorithms that differ in how they filter and apply the recursive search for an isomorphism. One example is BLISS.
However, the benefits are restricted to rather difficult cases unlikely to occur in practice (and it's not strictly better, meaning that, as far as I understand it, BLISS' recursive search will work well for some cases, NAUTY for others).
Are there any conditions that are sufficient to determine an isomorphism between two graphs?
As quasi mentions, there's no known finite set of invariants that can be computed in polynomial time. Again however, many simply invariants are sufficient to find (or reject the possibility of) an isomorphism in all but the most synthetic of cases. For random graphs, for example, a very simple linear-time algorithm exists for deciding isomorphism.
However, just to add: a recent (and quite famous) result by Babai states that there exist quasi-polynomial time algorithms for the general case. (I'm not sure, however, that the theoretical result reveals a practical algorithm; again, previously mentioned algorithms are efficient in practice).
