3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Calculate the spectrum of eigenvalues of the adjacency matrix for both graphs. If these spectra are different then the graphs are not isomorphic. $\endgroup$ – Donald Splutterwit Aug 27 '17 at 9:42
  • $\begingroup$ Thanks, did not know this necessary condition! $\endgroup$ – DanieleMS Aug 27 '17 at 9:44
  • $\begingroup$ I have actually used this criteria in a computer program to generate trivalent planar graphs. I am not sure if it works the other way around ... a bit like different knots having the same polynomial invariant ! $\endgroup$ – Donald Splutterwit Aug 27 '17 at 9:49
  • 3
    $\begingroup$ @DonaldSplutterwit : It doesn't work the other way round - there are pairs of co-spectral graphs that are non-isomorphic. eg math.stackexchange.com/questions/1677966/… $\endgroup$ – gilleain Aug 27 '17 at 11:12
  • 2
    $\begingroup$ A perhaps more interesting question is whether there are conditions that are sufficient to determine that two graphs are not isomorphic. See this question on cstheory. $\endgroup$ – Yuval Filmus Aug 27 '17 at 13:26
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.