🚀 go-pugleaf

Here is a possible counterexample to Gismondi and Swart's algorithm
for graph isomorphism.

We can think of the $s_{a,b}$ as relating the vertices a and b, giving
the degree to which a ``fuzzy isomorphism'' maps a to b.  We can think
of $t_{a,b,c,d} as relating the edge (a,b) of one graph to the edge
(c,d) of the other graph.  It's the degree to which a ``fuzzy
isomorphism'' maps (a,b) to (c,d).  Gismondi and Swart give an
associated linear programming problem in which a number of reasonable
linear inequalities are imposed on these values to try to characterize
isomorphism as closely as possible.

Let G1 be a graph consisting of two disjoint cycles of length n.  Let
G2 consist of one cycle of length 2n.  Then, the corresponding linear
programming problem of Gismondi and Swart is solvable with a solution
vector consisting entirely of 0 and .5 values.  Each vertex in G1
corresponds to two vertices in G2 by the fuzzy isomorphism.  Each
vertex in G2 corresponds to two vertices in G1 by this fuzzy
isomorphism.  The idea is that as you go around the long cycle in G2,
you go around each of the short cycles in G1, twice.  Also, it's not
possible to reduce any of the .5 coefficients to 0 without increasing
some 0 coefficient.  Of course, the graphs are not isomorphic.

Let H1 consist of disjoint copies of G1 and G2.  Let H2 be isomorphic
to H1.  Consider the linear programming problem corresponding to
showing that H1 is isomorphic to H2.  One possible solution to this is
the true isomorphism.  The other one is obtained by two copies of the
solution for G1 and G2 above.  So the G1 in H1 is related to the G2 in
H2 and the G2 in H1 is related to the G1 in H2.  Let's consider this
second solution.  All its values are 0 and .5.  Furthermore, it does
not cover a permutation, though one exists.  In addition, it is not
possible to reduce any of the .5 values to 0 without increasing some 0
value.

We can even make G1 and G2 and H1 and H2 connected, by adding a new
vertex connected to everything else.  Also, by extending this idea,
considerably more complicated counterexamples can be found.

I don't see any way that Gismondi and Swart's algorithm can
distinguish between these two cases, though I don't fully understand
their method.  So it seems to me that their approach is wrong and even
the algorithm is incorrect.  Of course, an implementation might happen
to give the right answer because of the solutions it happened to find.
So it seems that their approach cannot be saved except by some
fundamentally new ideas.

However, consider the set of pairs (G1, G2) of graphs such that the
associated linear programming problem has a (fractional) solution.
This seems to have a fairly restricted structure.  It also includes
the pairs of isomorphic graphs.  So maybe this linear programming
problem can be used as a preprocessing step for a graph isomorphism
algorithm.

	Dave Plaisted