1
$\begingroup$

In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is exponential, one usually has a polynomial running time.

I was hoping that the situation is similar in the case of labeled graphs. However, I have a really hard time to find any reference which proposes an ``practically efficient'' algorithm.

Remark: Here, we require that the isomorphism preserves the labels. That is, an isomorphism between two finite automata/process algebra terms would imply that the automata/terms are essentially ``equal up to renaming of the nodes''.

The only reference I found was the one in Wikipedia that states the the isomorphism problem of labeled graphs can be polynomially reduced to that of ordinary graphs. The underlying paper, however, is more about complexity theory than practical algorithms.

I am missing something, or is it really the case that the there are no efficient ``heuristical'' algorithms to decide whether two labeled graphs are isomorphic?

Any hint or reference would be great.

Best wishes, Max

$\endgroup$
1
$\begingroup$

I think the problem is that you are confused about what an "unlabelled graph" is. A graph consists of a set of vertices $V$ and a set of edges, each of which is an unordered pair of vertices. I am never entirely sure what people mean when they use the term "unlabelled graph". As a data point, the definition at http://mathworld.wolfram.com/UnlabeledGraph.html is confusing throughout and wrong in parts.

In this context the most useful interpretation of "unlabelled graph" is that it is an isomorphism class of graphs. (We say isomorphism "class" because it need not be a set.) Two isomorphism classes are either equal or disjoint - it makes no sense to speak of isomorphism of isomorphism classes. If the isomorphism classes of $G$ and $H$ are equal, then the graphs $G$ and $H$ (as defined above) are isomorphic.

The short summary is as follows: any algorithm for graph isomorphism you come up with quickly will take graphs as inputs, not "unlabelled graphs".

$\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.