Re: Need Graph Isomorphism Algorithm De-bunked

fgrieu wrote:
Bill Cox asked:
Somebody, please, show me two graphs which are hard
to compare!

At the end of this message are three 25-vertices graphs
that will give a hard time to the algorithm now at
http://www.billrocks.org/ideas/

This is a variation of my earlier counterexample:
one ring of 24 vertices for A, 2 independent rings of
12 vertices for B, both with an extra vertex connected
to all the others. C is a shuffle of B.

The problem exhibited is really only about the "2*D"
number of iterations, which I (now) think is insufficient.
My counterexample graphs have D=2. Yet with 4 steps in
the outer loop of the "hash iteration", the hashes for
all but one node are equal, and the hashes are the same
in all three graphs. The hashes are thus not enough to
recognize A from B, or to reorder B and C into a canonical
graph.
>
> I have no counterexample to the lazy version of the algorithm,
> where we loop N times rather 2*D. I have no conjecture on
> a minimum, but my counterexample implies it is at least
> in the order of N/4.

I take it that D is Diameter, defined as

maximum over i,j of (length of shortest path between node i and node j).

We could call that the Inner Diameter and also define an Outer Diameter as

maximum over i,j of (length of any path between node i and node j in which no node appears twice).


You've shown 2*ID iterations are not always sufficient. Are OD or OD+1 iterations sufficient?
I'm sure there are efficient algorithms for determining ID, but I don't know about OD. Of course, if one does go to the trouble of determining OD for each of two graphs, and gets different values, then the graphs are immediately non-isomorphic.

--Mike Amling
.

Relevant Pages

  • 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: exponential question
    ... A proof of the Collatz Conjecture has so far been ... easily be resolved by finding a counterexample. ... sequences without regard ... I HAVE investigated certain exponential iterations. ...
    (sci.math)
  • Re: Surrogate factoring, complete theory
    ... Is this the algorithm?: Given odd composite M not the square of a prime (or ... does the square-of-a-prime business not matter anymore?): ... the smallest counterexample is M=851 at j=2. ...
    (sci.math)
  • Re: Surrogate factoring, complete theory
    ... Is this the algorithm?: Given odd composite M not the square of a prime (or ... does the square-of-a-prime business not matter anymore?): ... the smallest counterexample is M=851 at j=2. ...
    (sci.crypt)
  • Re: An algorithm with Minimum vertex cover without considering its performance
    ... thinking of as a counterexample to the OP's new broken algorithm is ... The OP's new algorithm, AIUI, would take ... random graphs to check if there are any violations: ... Randomly generate a graph; ...
    (comp.programming)