Re: Need Graph Isomorphism Algorithm De-bunked

fgrieu wrote:
Mike Amling wrote :
I've coded up something I think is equivalent to what you
suggest. It works for up to 7 nodes (simply connected,
undirected, no loopback), but for 8 it only found 10126
equivalence classes, not 11117. I'll look again at the code
to see if something obvious is amiss.

My intent was to write an equivalent to the (second)
Bill Cox algorithm that you verified up to 8 nodes, except
not relying on a hash. I'd bet the problem (assuming it is
not in your implementation) is in my rendering of Bill Cox's
algorithm, not in the removal of the hash. Maybe I should
have used Bill Cox's code as a basis, rather than his text.
I'll check this in more detail.

The only data that you keep is the "result" concatenation of sorted unique "longhash"es (bad name; They're bit strings formed by concatenation, and not hashes.), right? I'm discarding final values assigned to the nodes. There is no marker between the list from one iteration and the appended list from the next iteration, but none should be necessary. And, mea culpa, I kept only a 32-bit hash of the results, not the results themselves (but I can hardly believe there've been 991 collisions).

It would help if you could give two graphs that are not
distinguished by your new code, but are distinguished by
the previous version (is it Bill Cox's?).

Yeah, when I saw that 10,126 I immediately regretted not keeping any data from previous runs. It will take a while.


I notice a fun thing: when using any variant of the algorithm
to compare two graphs, we can detect with certainty when the
algorithm fails, as follow.

We use the algorithm to produce a hash for each vertex.

If these hashes are not identical within order, we have
proved the graphs are not isomorphic.

"proved" to the point where I believe it, but I haven't seen a formal proof.

Else, we reorder both graph's matrix according to
nondecreasing hashes. If the reordered graphs are equal,
we have proved the graphs are isomorphic.

Else, the algorithm failed.

I think you have to specify more than "nondecreasing". The reordered graphs are equal iff you have established an isomorphism between the two graphs, and to do that you have to cope with Bill Cox's automorphism issue. E.g., two graphs that are each 4 nodes connected in a ring have only 8 isomorphisms, but all the node hashes are same and there are 24 ways to sort them nondecreasing.

--Mike Amling
.

Relevant Pages

  • Re: Is graph isomorphism in P?
    ... algorithm runs in polynomial time. ... graphs which are "pathological", so most of the time, you can solve NP- ... This is also why the average running time is not a good measure; ... isomorphism problem, where you only look at graphs with at most 400 ...
    (sci.math)
  • Re: Is graph isomorphism in P?
    ... algorithm runs in polynomial time. ... Fra invites people to post graphs to test his isomorphism program, ... Anyway, I've no problem to solve 600x600 or 1000x1000 MI istances, ...
    (sci.math)
  • Re: (Probably flawed) Polynomial time Graph Isomorphism
    ... On random input graphs graph isomorphism ... Note that testing degree sequences is a deterministic algorithm. ... The problem here is the algorithm relies on a hash function, ...
    (comp.theory)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... equivalence classes, not 11117. ... Bill Cox algorithm that you verified up to 8 nodes, ... not in your implementation) is in my rendering of Bill Cox's ... It would help if you could give two graphs that are not ...
    (sci.crypt)
  • Re: Is graph isomorphism in P?
    ... "In this site you will not find the algorithm or any ... algorithm fails to find the isomorphism, ... Fra invites people to post graphs to test his isomorphism program, ...
    (sci.math)