Re: Need Graph Isomorphism Algorithm De-bunked
- From: "Ben Livengood" <ben.livengood@xxxxxxxxx>
- Date: 30 Sep 2006 14:25:23 -0700
After the equivalence class of equally hashed vertices has been
created, each component of the graph should be considered as a second
equivalence class over the vertices and be intersected with the first.
Then the vertices with equal hashes should be ordered according to the
component they are in, which are sorted by size. For instance three
rings of size 5 generate 15 equivalent vertices but three components of
size 5. The vertices are ordered into groups of 5 depending on which
component they belong to, and the final result of intersecting the
equivalence classes is output along with the sorted graph, perhaps as a
vector of size N containing equivalence classes for the corresponding
vertices. Any representation that describes the boundaries of the
equivalence classes would suffice. As far as I can tell this still
preserves the total order of the hashing, because the final sorting
step is only needed to separate individual components of the graph, it
maintains an order that hashing alone could have produced under a
permutation of the vertices, and by sorting equivalence classes by size
a total order is created since any equally sized equivalence class
containing vertices with the same hash should be swappable with any
other from the same component.
Note that within each equivalent set of vertices, the equivalence
classes over those vertices must be sorted by the graph component the
vertices belong to, otherwise it would might be possible for graph A to
have components A1 and A2 mixed up in order with graph B's components
so that in the final order one graph has A1B1A2B2 and the other has
B1A1A2B2. I think this can only happen in the case that A1 and B1 have
the same hash, but the size of the equivalence classes for A1,B1 and
A2,B2 differ. I don't know if this is possible, since subparts of a
graph with different numbers of vertices should not generate the same
vertex hash results. If it turns out to be a problem the graph can just
be split into its connected components and hashed individually. I don't
see any problems with ordering graph components by their final hash
affecting the isomorphism decision. In fact, for a database of graphs
it might prove useful to only hash connected graphs and test trial
graphs for isomorphism only after separating them into their components
anyway.
Mike Amling wrote:
....
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.
Is same-equivalence-class the only criterion for this "pick"? If not,
what are the criteria?
Yes, same-equivalence class is all that's necessary. For instance, if
there is only one vertex in an equivalence class of graph A, there must
exist a matching vertex in the same valued equivalence class in graph
B, and by sorting with the hash they must be in the same position in
the output which suffices to identify them as equivalent. If there are
multiple vertices in an equivalence class E in A, there must be an
equal number of vertices in the corresponding equivalence class F in B,
and by the sorted hash the equivalence classes must overlap exactly.
Since equivalent vertices are indistinguishable to the hash, then if
the hash determines isomorphism it doesn't matter which vertex in an
equivalence class of graph A is first matched with the same equivalence
class in an isomorphism of A. Obviously once vertices start being
mapped to each other this will no longer be the case and the edges of
the graph must be taken into account.
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.
You could be going back to step 1 a lot. The equivalence class does
not even restrict Y to being a neighbor of M[X]. The probability of M[1]
being a neighbor of M[0] is 2/99. I think the OP's matching algorithm
has a better chance of being in RP.
I don't think I fully specified the algorithm, because the only way for
it to work is to ensure that Y is a neighbor of M[X]. Let me try again:
3. for a mapped vertex X in A, Y is the equivalent vertex in B as
indicated by M[X]=Y. For each edge from X to X' in A, do the following:
3.1 if M[X'] is defined, repeat 3.1 with the next X'. If no X' remain,
then pick another X go to step 3
3.2 Let E=Va[X']. For all Y' in B such that Vb[Y']=E and for all i no
M[i]=Y', do the following:
3.3 If the edges between X and X' do not match the edges between Y and
Y' in B, repeat this step with the next Y'. If no Y' remain, then the
graphs are nonisomorphic [1]
3.4 Set M[X']=Y', and go to step 3.
[1] If I am right about step 1 always working and the algorithm is
correct, then this is true because every step is deterministic and
there is no other way to try mapping the vertices that is not
isomorphic to what was already tried. In other words, permuting the
vertices in equivalence classes will not allow a mapping to be created,
which implies that no permutation of the vertices (while still sorting
them by their hash result) will result in graph equality, so there is
no isomorphism.
The equivalence class only tells the algorithm which set of vertices in
B to pick from. If the edges between X and X' match the edges between Y
and Y', and Y' is unmapped, then X' can be mapped to Y'. This is
straightforward for graphs without automorphisms, since each vertex is
a singleton in its equivalence class. For disconnected graphs with no
isomorphisms on its components, it is also straightforward since the
components are in different equivalence classes sorted by component.
For graphs with multiple permutation groups, as one vertex from a
permutation group is mapped, the valid permutations in other groups
must depend on the choices already made. Outside of step 1, any
arbitrary mapping choices directly correspond to a choice of which
graph permutation to select. I hypothesize that if the group
represented by graph automorphisms has order n, then the product of all
possible choices at every step in the algorithm must equal n. I am
nowhere near being able to prove this, but I think any algorithm that
decides graph isomorphism must at least pick one permutation out of the
permutation group. The problem with the proof will be proving how each
choice affects the number of other choices available at future steps.
Ben Livengood
.
- References:
- Re: Need Graph Isomorphism Algorithm De-bunked
- From: Ben Livengood
- Re: Need Graph Isomorphism Algorithm De-bunked
- From: Mike Amling
- Re: Need Graph Isomorphism Algorithm De-bunked
- Prev by Date: Re: What's wrong with AES?
- Next by Date: Re: What's wrong with AES?
- Previous by thread: Re: Need Graph Isomorphism Algorithm De-bunked
- Next by thread: Re: Need Graph Isomorphism Algorithm De-bunked
- Index(es):
Relevant Pages
|
