Re: Need Graph Isomorphism Algorithm De-bunked

Bill Cox wrote:
fgrieu wrote:
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

I made one small addition to the algorithm since you posted your formal
version. I didn't think it was necessarily important, but I required
it to show that when two graphs are reported isomorphic by the
algorithm, that they will be. At each step, I also hash into the hash
at each vertex the iteration step number. In your small ring, values
coming back to the original node will have different hash values
because of this.

I ran the above graph through the latest code (now posted), and it
determines they are different. I have spent a couple more hours trying
to find small manually generated counter examples (which I feel do
exist), but haven't. Next, I'll run it on the hundreds of graphs from:

http://amalfi.dis.unina.it/graph

I've also added code to resolve the isomorphism when the graphs have
auto-morphisms. Now, if the code runs into a counter-example, and it
generates a bad isomorphism, it will report the error.

I don't understand that there's a problem with auto-morphism. If two nodes end up with the same hash, then the graph with those nodes exchanged is isomorphic to the original graph, which is as it should be. And the nodes of any other graph isomorphic to that graph will generate the same node hash values with the same duplicate values.

--Mike Amling
.

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: Need Graph Isomorphism Algorithm De-bunked
    ... unless I misunderstood the OP's algorithm, ... The left is a ring of 6 vertices, ... assigning the same value to all vertices in the two graphs. ... and you get a fully-connected counterexample. ...
    (sci.crypt)
  • Re: Common points of f and f^{-1}
    ... The common points of their graphs are always on the line y=x? ... Much simpler counterexample: ... Math Tutor on the Internet and in Central New Jersey and Manhattan ...
    (sci.math)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... The algorithm produce a bit string from an undirected graph ... The output of isomorphic graphs is identical. ... throwing away the values and just keeping the lists. ... the hash is distinguishable from a random oracle. ...
    (sci.crypt)
  • Re: New algorithm for the isomorphism of graphs
    ... of the planar ones. ... of two trees, or the case of two planar graphs, then you can solve the ... since the Graph Isomorphism problem would be known to be in P. ...
    (sci.math)