Re: (Probably flawed) Polynomial time Graph Isomorphism

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.

True. Technically, this algorithm wouldn't be in 'P', which requires
absolute worse-case performance to be polynomial. So, an algorithm
that repeatedly rolls a million-sided die, and only ends when the
result is not 1, technically is not in P. Is 'RP' the correct class.
Here's the Wikipedia link:

http://en.wikipedia.org/wiki/RP_%28complexity%29

Has graph isomorphism been shown to be in RP? If not, this could be a
new result. Of course, being in RP is nearly as good as being in P,
from a usability point of view.



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?

Only if there is a hashing collision (or more likely, because I've got
this algorithm wrong). Essentially, a vertex label (XOR of all it's
hash results) depends on the structure of the graph and the hashing
function. Any change in the graph will change the hashing (I think).

I think the collision-rates for the hash functions would have to be
proven out, but for the asymmetric hash, SHA-1 could be used, which has
a long history of being nearly collision free, probably good enough for
practical use. Actually, I think much simpler hashes are good enough
for practical use: we're not trying to make it hard for super-computers
to find collisions, just unlikely to accidentally run into one.

Vertices that map to different vertices in automorphisms do wind up
with the same hashes, since structurally, they are in symmetrical
positions. I think these can be eliminated without increase the order
run-time, though I have not implemented the code. Basically, any two
vertices in the two graphs with the same hash value should be legal to
assign to each other. However, after that assignment, you can't keep
assigning other nodes with the same labels to eachother. For example,
if comparing graphs which are just squares, with four vertices, and
four edges, you can arbitrarily make the first assignment, but after
that, you have to be more careful. To take this into account, new
labels would have to be generated. This can be done by assigning the
newly matched nodes a random hash value, and propagate hash values
through the graphs as before. Then, XOR the new hash values into all
the vertex labels. I'll try to find time to add this code.

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.

The adjustments made to the vertices is always the same. I just hash
their degree with a big constant (that I rolled randomly). That makes
their hash values unique (within the graph) at the start of a hashing
iteration, but matching nodes in the other graph will also use the same
hash value when they are start-points. Since I always apply the same
modification to the hash values on the start-point nodes, matching
nodes in both graphs will have the same hash results. This is somewhat
verified by testing.

.

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)