Re: Need Graph Isomorphism Algorithm De-bunked
- From: "Ben Livengood" <ben.livengood@xxxxxxxxx>
- Date: 29 Sep 2006 16:08:16 -0700
Mike Amling wrote:
The only data that you keep is the "result" concatenation of sorted
unique "longhash"es (bad name; They're bit strings formed by
concatenation, and not hashes.), right? I'm discarding final values
assigned to the nodes. There is no marker between the list from one
iteration and the appended list from the next iteration, but none should
be necessary. And, mea culpa, I kept only a 32-bit hash of the results,
not the results themselves (but I can hardly believe there've been 991
collisions).
The first of the two graphs François Grieu provided in his reply to me
only had longhash differences in the first and second iterations for
the 8 vertices of the cube, and after that all 8 longhashes are equal.
The differences between the longhashes of the top and bottom vertices
only differed by a few bits, so it's possible that a 32 bit hash isn't
long enough. When I implemented François's algorithm I used strings of
integers instead of creating bitstrings since it seems to preserve the
sorting order of the vertex values and was simpler to implement, but I
haven't proved that it's equivalent and I may also have gotten
different results than the algorithm he specified.
I think you have to specify more than "nondecreasing". The reordered
graphs are equal iff you have established an isomorphism between the two
graphs, and to do that you have to cope with Bill Cox's automorphism
issue. E.g., two graphs that are each 4 nodes connected in a ring have
only 8 isomorphisms, but all the node hashes are same and there are 24
ways to sort them nondecreasing.
I think that outputting sorted vertices and an equivalence relation
over the vertices might work. To generate a mapping from one graph to
another isomorphic graph just map vertices one at a time from one graph
to the other, and as each vertex is mapped all its neighbors can be
mapped as well. By restricting the available choices of mappable
vertexes to the equivalence class I think it is deterministic and in P.
The algorithm would work as follows:
Assume two graphs A and B of equal size and matching hashes.
Remove duplicate vertex hash results from the final hash, making an
equivalence relation over the vertices, e.g. an array Va and Vb with
Va[i] set to the index of the new duplicate-free hash result array
(which was sorted by the original algorithm), and similarly for Vb.
Generate an empty array M of size N for mapping vertices from A to B.
Assume M[i]=j implies vertex i in A is mapped to vertex j in B.
1. Pick an initial vertex from the same equivalence class of both
graphs, and map them to each other. I am not sure this step is in P.
There may be graphs where there are no equivalence classes containing
only a single vertex, which means every combination of vertices from A
and B from the smallest equivalence class must be tried to see if a map
can be found.
2. Pick a mapped vertex (M[i] is defined) from A that has unmapped
neighbors. For each unmapped neighbor X:
3. Let E be the equivalence class X belongs to in A. Pick an unmapped
vertex Y from the corresponding equivalence class of graph B. E.g.
Va[X]=Vb[Y] and there does not exist i such that M[i]=Y. Since Va and
Vb are sorted, equal indexes should imply corresponding equivalence
classes. Set M[X]=Y, and go to step 2 if there are more unmapped
neighbors. If at any step an edge implies that the mapping is incorrect
(X has only one choice Y in the other graph, but M[X]!=Y), either the
algorithm has failed or step 1 must be repeated with a different
combination of starting vertices.
4. If there are no unmapped neighbors of any mapped vertex, the graph
is disconnected, so go to step 1.
I'll try this tonight and see if it can generate a map for all
permutations of a graph back to itself. I don't think step 1 will
actually be a problem because if the choice of starting vertex
mattered, the graphs would likely not be isomorphic. The problem with
my earlier attempt was that no internal structure within equivalence
classes of vertices was possible to express with the equivalence
relation alone. Hopefully this fixes it.
Ben Livengood
.
- Follow-Ups:
- Re: Need Graph Isomorphism Algorithm De-bunked
- From: Mike Amling
- Re: Need Graph Isomorphism Algorithm De-bunked
- Prev by Date: Re: Questions about Shamir secret sharing
- Next by Date: Re: Self-shrinking MT19937 as stream cipher
- Previous by thread: How to approach decrypting Ciphertext
- Next by thread: Re: Need Graph Isomorphism Algorithm De-bunked
- Index(es):
Relevant Pages
|
