Re: (Probably flawed) Polynomial time Graph Isomorphism

Bill Cox wrote:
I don't understand the modified hash phase.

Suppose G1 and G2 have the same initial hashes.

I pick a node in G1 to modify. Now what do I do? Try modifying each node
in G2 the same way to see if the hashes now match? Then what, if I get
multiple matches?

Patricia

Thanks for the reply!

I didn't describe the fix to the algorithm well at all. I'll reword it
on the blog. Basically, the problem in the first version of the
algorithm was that if we have graphs with the same number of vertices
and when every vertex in both graphs have the same degree, then there's
no initial difference in the hash values, and they stay in sync. The
original algorithm failed in this case.

To get around this problem, I ran the algorithm once per vertex in the
graph. Each time, I started with vertex hash values equal to its
degree, except for the one vertex chosen as the start-point for that
iteration. That vertex would start with a different hash value than
the rest, for example it could be a large fixed constant. Then, hash
values change throughout the graph and settle to unique values on each
node, unless the graph is automorphic, or in the unlikely case of a
hash collision.

A polynomial time algorithm must get the right answer, within the time
bound, even for the worst possible input. That means, for example, that
you would need to show both correctness and the time bound for the worst
possible combination of hash collisions.


To generate a label for a vertex, I XOR the hash results from each
iteration together. Thus, it doesn't matter what order I do the hash
iterations in either graph, and matching vertices should wind up with
the same hash values.

But can't non-matching vertices also end up with the same value? What
happens if, when you do the XOR, both graphs contain the same large
number of vertices all with the same hash code? Can you show that it
won't happen?

Also, if you apply different adjustments to different vertices, you
could end up with different hash codes for matching vertices in
isomorphic graphs, just because the adjustments you applied to the
matching vertices were different between G1 and G2?

I'm afraid I'm failing to see any way of adjusting the hash codes avoids
both problems.

Patricia
.

Relevant Pages

  • 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: Need Graph Isomorphism Algorithm De-bunked
    ... At the end of this message are three 25-vertices graphs ... the cost has raised to Ofor constant hash width; ... giving a longhash. ... The result of each "hash iteration" is the concatenation of ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... Since graph isomorphism is a long studied problem with no known ... For 2*D iterations, update each vertex's hash value, by hashing it with it's neighbor's hash values, and the iteration number. ... does that mean that you first XOR all a node's neighbors' current hashes together and then hash the result in with the node's current hash and the iteration number? ... It generates the same hash for each node of two non-isomorphic graphs if the two graphs have the same number of nodes and all the nodes on the graphs have the same degree. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... We use the algorithm to produce a hash for each vertex. ... proved the graphs are not isomorphic. ... Comparing two ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... We use the algorithm to produce a hash for each vertex. ... proved the graphs are not isomorphic. ... Comparing two ...
    (sci.crypt)