Re: (Probably flawed) Polynomial time Graph Isomorphism

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.

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.

Does that make sense (or even work)?

.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... The proof that isomorphic graphs give identical hash, ... We'll be running this version of the algorithm, ... [values of each node in sorted order ]. ... value'@the same for graph G'. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... which correctly differentiates all of the examples you've ... The proof that isomorphic graphs give identical hash, ... [values of each node in sorted order ]. ... note value'@the same for graph G'. ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... an accidental hash collision, I think we can get rid of any ... The algorithm is stated for an undirected graph only ... a "result" bit string, initially empty. ... For each node, assign to longhash its value, followed ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... an accidental hash collision, I think we can get rid of any ... The algorithm is stated for an undirected graph only ... a "result" bit string, initially empty. ... For each node, assign to longhash its value, followed ...
    (sci.crypt)
  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... preimage resistant hash function accepting a graph as ... exchanging any vertices leaves the hash ... implying that computing and comparing two such ... width w, supposed collision and preimage resistant, ...
    (sci.crypt)
Quantcast