Re: Need Graph Isomorphism Algorithm De-bunked

In article <efgqn6$dd6@xxxxxxxxxxxxxxxxxxxxxxx>,
Mike Amling <nospam@xxxxxxxxxx> wrote:

François Grieu wrote:
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.

I stand by "proved". The proof, by induction, that the graph hash
produced by all variants stated so far is invariant under graph
isomorphism, seems quite straightformard;
this is all that is needed to proove that different hashes imply
non-isomorphism.

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.

You are right. What I stated is strictly speaking true, but the
"algorithm failed" box is reached hopelessly often.


François Grieu
.

Relevant Pages

  • 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: 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)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Bill Cox algorithm that you verified up to 8 nodes, ... not in your implementation) is in my rendering of Bill Cox's ... proved the graphs are not isomorphic. ... 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. ...
    (sci.crypt)
  • Re: Sean PItman and nested hierarchy
    ... if God created life then the patterns in the ... the concept of "uniform probability distribution" is well-defined. ... Since the vast majority of the graphs ... Yes, it can, depending on the algorithm used. ...
    (talk.origins)