Is there any algorithm to find Isomorphism function between two graphs?

Question

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.

Answer 1

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.

Answer 2

As other commenters have pointed out, there is no simple algorithm for all graphs that runs very fast. I know that 'very fast' is vague, but I'm not able to discuss the complexity of the problem particularly well.

However...

For many classes of graph - such as those of bounded degree, treewidth, etc - there are various algorithms to determine an isomorphism function that will map one to the other.

One approach is based on partition refinement. This is quite well described here but I'll give a short description as I understand it. Note that this is broadly the technique used by nAUTy and similar programs (bliss, traces, saucy) to compute graph isomorphisms and automorphisms.

What is required for isomorphism between two graphs - G, H - is a canonical labelling (cl) for each such that cl(G) = cl(H). If you simply wanted to test for isomorphism, then you could calculate a 'certificate' for both. For a pair of trees, this is as simple as a string formed by recursively building up from the leaves (labelled '01'), sorting at each stage, until you get to the root (see the description starting "For trees..." in the wiki page for canonical labelling).

To get the actual mapping, we need to create an actual canonical labelling - in other words, choose a particular permutation for each graph that 'relabels' it into the canonical form. This is where partition refinement comes in. Starting with a root partition - such as the partition of the vertices by degree - we successively 'refine' the partition until we get permutations. Permutations are, in this view, just 'discrete' partitions with one vertex in each block.

Here, a partition A is 'finer' than another partition B if we have split up one or more of the blocks of A to get B. Depending on how we choose which block to split next, and how the blocks are ordered in the refined child partition, we get a particular labelling. The refinement procedure forms a tree of partitions, with permutations as the leaves - and we choose (say) the first one we reach.

There is obviously a lot more to this subject, but a good introduction to this I found in this book called "Computational Algorithms : Generation Enumeration and Search" by Kreher and Stinson.

Answer 3

If you had a polynomial-time algorithm (with a known polynomial complexity bound, say $C n^p$) to find an isomorphism for a pair of graphs that are in fact isomorphic, you could use that to determine in polynomial time whether two graphs are isomorphic. Namely, you run the algorithm with a time limit of $C n^p$, and check whether it produces an isomorphism. Note that it's easy to check in polynomial time whether something is an isomorphism of the graphs.

If your two graphs happen to be isomorphic, then by assumption the algorithm will produce an isomorphism within that time limit, and your isomorphism checker will verify that it is an isomorphism. If they aren't, then what can happen? Either the algorithm will run over the time limit, or it will stop within the time limit with some result (perhaps an error message, or maybe something that isn't an isomorphism), and your isomorphism checker will show that this isn't an isomorphism.

As others have mentioned, we don't curently have a polynomial-time algorithm to decide graph isomorphism, and there is some reason to believe that no such algorithm exists.

However, that is all worst-case complexity. In more "typical" cases, graph isomorphism is relatively easy. See e.g. McKay and Piperno, "Practical Graph Isomorphism II".

Answer 4

The previous answers have provided useful information about the nature of the graph isomorphism problem, but it seems that you are also looking for a reliable algorithm to use for low-order graphs. I (among many others) have developed such an algorithm for planar triangulations that I have tested on all isomorphism classes for 4-connected planar triangulations through order 16 and all isomorphism classes for 5-connected planar triangulations through order 24. It has been implemented in APL, unfortunately not terribly useful to most users. But I thought a brief description of my algorithm might help you code your own quite quickly.

It is useful to begin by testing to see if two planar triangulations $A$ and $B$ of order $n$ are rather obviously non-isomorphic. I use the following three tests:

(a) the $n$-vector of the vertex degrees for $A$ and $B$ each in non-decreasing order; if they do not match element by element, the graphs are not isomorphic;

(b) the distributions of the degree-sums for the $3n-1$ edges in each of $A$ and $B$; if they do not match, the graphs are not isomorphic;

(c) the distributions of the degree-sums for all diamonds (4-cycles with an edge between one pair of opposite vertices) in each of $A$ and $B$; if they do not match, the graphs are not isomorphic.

If $A$ and $B$ pass these preliminary tests designed to weed out obvious non-isomorphisms, my algorithm moves on to a more detailed test of the LOCAL properties of vertices in each of $A$ and $B$. Each vertex is assigned a list of five attributes and then the $n$-item list for $A$, one item for each vertex in $A$, is compared with the $n$-item list for $B$, one item for each vertex in $B$. If there is any one-to-one matching correspondence of elements between the two lists, the two graphs are deemed to be isomorphic.

This more detailed test will produce failures for sufficiently high $n$ because the local degree properties specified in the list do not capture any aspect of graph structure at a distance greater than 4 from each vertex. However, the algorithm executes quickly and does not fail within any of the isomorphism classes I stated earlier. It may well succeed without failure for several higher orders for each connectivity, but I have not tested other than the 48,567 distinct triangulations in those classes.

Here is the list of five attributes I associate with each vertex $v$:

1. The degree $k$ of $v$.

2. The degree-sum for all the vertices in the $2k$-cycle of vertices that I call the "Sheriff's Badge" centered on $v$, a particular cycle which I shall define following the presentation of this list of vertex attributes.

3. The ordered sequence of length $2k$ of degrees of the vertices in the Sheriff's Badge. By ordered, I mean the sequence of degrees for the vertices in the cycle followed in one direction or the other around the cycle from a designated starting vertex in the cycle.

4. For each vertex in the Sheriff's Badge cycle, the degree-sum of its adjacent vertices that are neither $v$ nor any vertex in the Sheriff's badge itself. This attribute is represented as an ordered sequence, a $2k$-vector, each element a degree-sum.

5. The ordered sequence of item 2, a $2k$-vector, one element for each vertex in the Sheriff's Badge cycle.

The Sheriff's Badge for any vertex $v$ is determined by first determining the cycle $C$ adjacent to $v$ and then for each edge $xy$ in $C$ determining the vertex $w$ that forms the diamond $xwyv$. Let $v_1, v_2, ... , v_k$ represent the ordered sequence of vertices defining $C$, with $v_1$ the designated starting vertex. Thus, the various vertices labeled $w$ represent the "points" of the Sheriff's Badge: $w_1$ completes the diamond for edge $v_1v_2$, $w_2$ completes the diamond for edge $v_2v_3$, and so on, until $w_k$ completes the diamond for edge $v_kv_1$. It does not matter if several consecutive $w$ represent the same vertex; we do not eliminate duplicates. The Sheriff's Badge cycle is the ordered sequence $v_1, w_1, v_2, w_2, ... , v_k, w_k$.

In comparing the three cycles (those in items 3, 4, and 5) associated with each vertex in $B$ with the same three cycles with a vertex in $A$, it is necessary to test all possible rotations of the sequence of the cycles for $B$ (i.e. one position to the right, two positions to the right, and so on, with the identical rotation for all three cycles) with the cycles fixed as defined for $A$. It is also necessary to test such rotations for the cycles in $B$ in reverse order as well as forward order because they may have been computed for $B$ in the opposite sense of traversing the cycles in $A$. These comparisons are all handled trivially in APL.