# Is there an algorithm for determining when two graphs are isomorphic?

The title says it all. Is there such an algorithm? More generally, is there an algorithm for deciding when two objects are isomorphic in a particular category?

-
My knowledge of mathematical logic is weak, but as far as I know the first problem is NP (I don't know the formal definition of NP). As for the second question, a positive answer would imply the existence of an algorithm that differentiates between non-homeomorphic topological spaces. I really doubt this. –  Amr Aug 10 '13 at 21:25
@Amr: Thanks. Would you elaborate why existence of such an algorithm would imply the existence of an algorithm that differentiates between non-homeomorphic topological spaces? –  some1.new4u Aug 10 '13 at 21:29
Regarding the first problem, ofcourse there is the brute force solution. More precisely, Let $G,H$ be two graphs. If $|V(G)\not=|V(H)|$ then the two grphs can not be isomorphic. If $|V(G)|=|V(H)|$ then check all $|V(G)|!$ bijections and see if any one of them is a graph homomorphism –  Amr Aug 10 '13 at 21:32
Ah I see. Without good restrictions on your category you will get trivial answers. For example, Consider the category $\scr{C}$ that has one object. For this category, we know an algorithm that can tell us if two objects are isomorphic or not. –  Amr Aug 10 '13 at 21:42

The upper triangle of a graph $G$ on $n$ vertices can be written out as a binary sequence of length $n(n-1)/2$, and hence as a binary integer. From the $n!/|\mathrm{Aut}(G)|$ distinct graphs isomorphic to $G$, choose the one that gives the least integer. This is an invariant of the isomorphism class, two graphs are isomorphic if and only if they give rise to the same integer.

-
Technically you should include a test that the two graphs have the same number of vertices, as adding a disconnected vertex wouldn't change the integer you've defined. –  Peter Taylor Aug 10 '13 at 21:44

Please, see new algorithm for graph isomorphism testing http://arxiv.org/abs/1004.1808

-
Welcome to MSE! It helps if you could perhaps summarize the algorithm, give the name and the title of the paper. Unfortunately, links change or get removed and if someone looks at this in the future, there may not be any details regarding this answer. Regards –  Amzoti Aug 11 '13 at 15:08
I expect that arxiv links are quite stable. Notice, however, that the abstract claims a polynomial time algorithm for deciding whether two graphs are isomorphic. As far as I know, the experts still consider the existence of such an algorithm to be an open problem, and a quick search on MathSciNet didn't turn up a published paper corresponding to this arxiv item. So I would recommend caution in relying on this result. I haven't looked into the proposed algorithm, so it may well be correct, but it does not seem to be generally accepted yet. –  Andreas Blass Aug 11 '13 at 15:22