Re: Need Graph Isomorphism Algorithm De-bunked

Mike Amling wrote:
François Grieu wrote:
On the positive side, **IF** the algorithm works save for
an accidental hash collision, I think we can get rid of any
possibility of collision, and still be in polynomial time
(as Mike conjectured then retracted).
I (snipped)

Last night I thought I understood what you are suggesting,
and if the algorithm works, it would put graph isomorphism
into P, not just RP. This morning I'm doubtful.

First, do I understand the what you suggest?

I did not quite recognize my idea. I'll paraphrase you,
at the same time fixing a flaw in my earlier description.
The algorithm is stated for an undirected graph only
(symmetric matrix), no loopy vertices (diagonal is 0).

0. Associated to each node we need
- a "value" in the range 0..n-1, assimilated to a
fixed length bit string of ceil(lg2(n)) bits;
- a "longhash" bit string;
- a "result" bit string, initially empty.
1. Repeat 2..5 with each node the special node in turn
2. Assign the special node the value 1. Assign all the other
nodes the value 0.
Repeat 3..4 some number of times (N? N/4?).
3. For each node, assign to longhash its value, followed
by its neighbors values in sorted order (duplicates
kept); longhash has length at most n*ceil(lg2(n)).
4. Make a list of all the longhash assigned in step 3.
Sort the list and remove duplicates (regard a shorter
string as strictly less than any longer string).
Assign each node a new value, which is the position of
its longhash in the list.
Append to the special node's result a bit string
reversibly coding the list (e.g. prefix each longhash
with a length prefix of appropriate fixed size, the
zero length coding end of list)
Notice that what we just appended is invariant under
graph isomorphism, and that it is enough to rebuild the
current longhash of each node from its current value.
5. Append to the special node's result the sorted list
of the values of each node in sorted order (duplicates
kept);
6. Sort all N results (duplicates kept, shorter strings
first), compute the whole graph's hash as a bit string
reversibly coding the N results (e.g. prefix each result
with a length prefix of appropriate fixed size). Notice
this graph's hash is invariant under graph isomorphism,
and enough to backtrack (except for a shuffle of the nodes)
the values and longhash assigned to each node, without
knowledge of the graph.

An alternative to step 6 is to output the graph in generic
order based on a sort of the results, making a much shorter
and useful representative of the graph's equivalence class
(this has been suggested by Bill Cox).
I however fail to convince myself that this is equivalent;
or that the "compare graph's hash" variant never falsely
declare graphs isomorphic, or that the "compare sorted
graphs" variant never falsely declare graphs non-isomorphic.

François Grieu

.

Relevant Pages

  • 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: multi application
    ... Before tis Im basically loading the form, adding a graph and user ... string[] status; ... && layValue> 0.9) ...
    (microsoft.public.dotnet.languages.csharp)
  • 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
    ... 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)