Re: Need Graph Isomorphism Algorithm De-bunked

Mike Amling wrote:
I think it is sufficient to represent the graph over the equivalence
class of its vertices. Let N be the number of equivalence classes over
the vertices in the graph.

Equivalence under what relationship? Is this related to automorphism?

As far as I can tell, the vertices that generate the same final hash
(before the vertex hashes are combinded to make the final graph hash)
are the vertices that are part of the permutation group of the graph's
automorphism group. Clearly any automorphism of the graph will generate
the same final hash, but my assumption is that for each automorphism
the vertices with equivalent hashes will stay within their own
equivalence class, but in a different order. This seems pretty
straightforward, since if two different permutations of a graph's
vertices produce different hash results for any vertex, the hash would
not preserve isomorphisms.

I am pretty sure that François Grieu's counterexample proves that the
equivalence classes alone are not sufficient to represent the entire
graph. However, I still think the equivalence classes can be used in
conjunction with a sorted graph representation to generate a mapping
between the vertices of two graphs. If this can be done deterministicly
it would constitute a proof that the algorithm cannot generate false
positives, since if the algorithm could always generate a vertex
mapping between graphs with equivalent hashes then those graphs must be
isomorphic by definition.

You mentioned in another post that sorting the graph matrix lexically
produced a unique representation for every graph under isomorphism,
which would be much more useful than trying to work with equivalence
classes. How were you determining the lexical order? Did automorphisms
cause any difficulty?

Ben Livengood

.

Relevant Pages

  • Re: Need Graph Isomorphism Algorithm De-bunked
    ... each component of the graph should be considered as a second ... equivalence class over the vertices and be intersected with the first. ... vector of size N containing equivalence classes for the corresponding ...
    (sci.crypt)
  • Re: Can this be done in SQL? Find the transitive relation
    ... I am strugling get the following done in SQL. ... http://www.bookpool.com/sm/0977671542, section on transitive closure ... There are several key graph concepts that would guide your intuition ... Figure 6.5: Reachability as an equivalence relation: graph from fig. ...
    (comp.databases.oracle.server)
  • Re: Expressions versus the value they represent
    ... particular relation of type DirectedGraph. ... Under interpretation let GRAPH(T) denote the graph ... think it is dangerous to confuse an equivalence class with its members ...
    (comp.databases.theory)
  • Re: help me understand this theorem
    ... > So all they are saying is that the relation of nodes being connected ... The utility of equivalence relations is that that they ... In the case of a graph, ... as equivalence classes. ...
    (sci.math)
  • Re: Sixth grade math
    ... Both equivalence and order relations are used to ... This is exactly graph a function which is defined as a set ... of ordered pairs blah blah blah, ...
    (sci.math)