Re: Need Graph Isomorphism Algorithm De-bunked

In article <egc7ud$osl@xxxxxxxxxxxxxxxxxxxxxxx>,
Mike Amling <nospam@xxxxxxxxxx> wrote:

Phil Carmody wrote:
You are checking that it actually detects isomorphisms too,
aren't you?
You've not explicitly said so. Else here's an O(1) algorithm
which correctly differentiates all of the examples you've
listed so far.

are_isomorphic(M1, M2) = are_identical(M1,M2)

Not to worry. Francois Grieu has proved that there are no false
negatives. (Je ne comprends pas la preuve. Elle implique beaucoup
d'onduler de main.)

The proof that isomorphic graphs give identical hash, with less
handwaving (gestes des mains), runs as follows.

Suppose two graphs G, G' with n nodes are isomorhic. That is,
there exists a permutation P on {0..n-1} such that
for all i,j G[i,j] = G'[P(i),P(j)].

We'll be running (say) this version of the algorithm,

0. Associated to each node we need
- a W-bit "value";
- a W-bit "temp";
- a W-bit "result".
1. Repeat 2..5 with each node (s) the special node in turn.
2. Assign the special node the value "all bits clear
except the last".
Assign all the other nodes the value "all bits clear".
Repeat 3..4 some number of times, say for t in {0..N-1}.
3. For each node (u), assign to temp the hash of
[the node's value, followed by its neighbor's
values in sorted order (duplicates kept)].
4. For each node, copy temp to value.
5. Set the special node's result to the hash of
[values of each node in sorted order (duplicates kept)].
6. Produce the overall result as the hash of
[outputs of all nodes in sorted order (duplicates kept)].


Note value[u]@(s,t) the value for node u at step 3 when
computing result for node s (variable of step 1), and at
iteration t (variable in step 2), for graph G; and note
value'[u]@(s,t) the same for graph G'.

We'll proove by induction that
value[u]@(s,t) = value'[P[u]]@(P[s],t)

This is true when t==0, since
value[u]@(u,0) == 1, value[u]@(s,0) == 0 when u!=s,
value'[u']@(u',0) == 1, value'[u']@(s',0) == 0 when u'!=s',
we choose u' = P[u], s' = P[s'] and get
value'[P[u]]@(P[u],0) == 1, value'[P[u]]@(P[s],0) == 0 when u!=s
thus value[u]@(s,0) = value'[P[u]]@(P[s],0).

If the induction property is true up to t, when performing
step 3 for node u and graph G, the node's value is the same
as the value when running step 3 for node P[u] and graph G'.
And the neighbor's values being sorted are the same for
graph G and G", save for order. Because the values are ordered
before hash, thus the hash insentitive to order, it follows
that at iteration t, after step 3, for all u,
temp[u] = temp'[P[u]]
and thus after step 4, the induction property is valid for
the next t.

Because the hash used at step 5 is insensitive to order, it
follows that at step 5, result[s] = result'[P[s]]

Because the hash used at step 6 is isensitive to order, it
follows that the overall result is identical for G and G'.


I which that a proof that equal graph hashes implies isomorphism
would be that simple.


Note: it's silly, but I stil do not have a running version
of the code, and have not checked the "strongly similar" graphs
by myself (seems we have two contributors in disagrement here).


François Grieu
.

Relevant Pages

  • Re: (Probably flawed) Polynomial time Graph Isomorphism
    ... I pick a node in G1 to modify. ... I didn't describe the fix to the algorithm well at all. ... no initial difference in the hash values, ... values change throughout the graph and settle to unique values on each ...
    (comp.theory)
  • 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)