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 isomorphic. 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)].


We'll note value[u]@(s,t) for 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 prove by induction that for all u,s and t in {0..n-1}
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, then 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, making the hash insensitive 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 insensitive to order, it
follows that the overall result is identical for G and G'.


I wish that a proof that equal graph hashes implies isomorphism
would be that simple, or even possible.


Note: it is silly, but I still 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 disagreement here).


François Grieu
[reposted with corrections]
.

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
    ... 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)