Re: Need Graph Isomorphism Algorithm De-bunked

Some thoughts later: unless I misunderstood the OP's algorithm,
it does not work. At least my variant does not work.
I found a counterexample. These two graphs are non-isomorhic,
but my algorithm fails to distinguish them.

0 1 0 0 0 1 0 1 1 0 0 0
1 0 1 0 0 0 1 0 1 0 0 0
0 1 0 1 0 0 1 1 0 0 0 0
0 0 1 0 1 0 0 0 0 0 1 1
0 0 0 1 0 1 0 0 0 1 0 1
1 0 0 0 1 0 0 0 0 1 1 0

The left is a ring of 6 vertices, the right is 2 independent
rings of 3 vertices. Problem is, the algorithm keeps
assigning the same value to all vertices in the two graphs.

The problem can occur even for fully connected graphs:
just complement the matrix except for the diagonal
and you get a fully-connected counterexample.

I retract all my previous posts in this thread.

Still I feel that the use of a crypto hash made insensitive
to order by sorting its input is a promizing technique
to recognize graph isomorphism.

François Grieu

.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... This is a variation of my earlier counterexample: ... My counterexample graphs have D=2. ... > I have no counterexample to the lazy version of the algorithm, ... You've shown 2*ID iterations are not always sufficient. ...
    (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)
  • Re: Sean PItman and nested hierarchy
    ... the concept of "uniform probability distribution" is well-defined. ... Since the vast majority of the graphs ... Yes, it can, depending on the algorithm used. ... Separate creation can produce any pattern whatsoever, including a nested hierarchy. ...
    (talk.origins)
  • 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: Sean PItman and nested hierarchy
    ... if God created life then the patterns in the ... Since the vast majority of the graphs ... Yes, it can, depending on the algorithm used. ... create a tangled loop in the graph. ...
    (talk.origins)