# Graph isomorphism problem for labeled graphs

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

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.