Re: (Probably flawed) Polynomial time Graph Isomorphism

Bill Cox wrote:
I've written a graph isomorphism program that determines if two graphs
are isomorphic. It runs in O(N^3).

Since graph isomorphism is a long studied problem with (AFAIK) no known
polynomial time solution, my algorithm is more than likely flawed. Any
help finding the flaws would be appreciated! The web site is

http://www.billrocks.org/ideas

Thanks!


The difficult examples are strongly regular graphs, e.g. Springer Lecture Notes Math 558, p 158 ff. Take two nonisomorphic strongly regular graphs (the smallest examples have 26 vertices) and apply your algorithm. Replace your hash function with a vector of the values generated during the iterationsd to see that there can't be a hash function that creates an appropriate labelling.
hth
Klaus

.