🚀 go-pugleaf

I'm posting this message for my father:

-------------------------------------------------------------------------


                     Graph Isomorphism et al

     Although we have not contributed to the comp.theory discussion
directly, we would like to publicly -- in open forum -- express our
appreciation to all those of you who have provided helpful dialogue
on a one-on-one basis regarding our graph isomorphism and N=1
papers.  It seems appropriate, moreover, to bring you all up to
date as to the current status of these papers.  There are several
aspects of the graph isomorphism paper and its relationship to the
N=1 paper which drew significant attention and the outcome of the
resulting dialogue is as follows:

     * Several people pointed out that corollary 1 was not fully
justified and possibly in error.  We are happy to report that all
those who have discussed this point with us are now agreed that it
is not in error and can be justified.  Strictly speaking, however,
it does need an additional lemma concerning the implications of the
Ta=b constraints.  The effect of these constraints is largely
benign in that all that they do is require some of the t[abcd] and
possibly some of the s[ab] variables to be zero.  Any solution to
formulation F3 which has a C_0 pattern or a C_0 sub-pattern, which
avoids these zeroes, thus implies the existence of a Q matrix
solution which likewise avoids these zeroes which, in turn, implies
that the graphs being examined are isomorphic.

     * Quite a few people have suggested that even if the graph
isomorphism paper is correct that this does not imply the
correctness of the N=1 paper.  We are happy to report that on this
point as well there is now complete agreement with all those with
whom we have discussed the issue.  If there is an LP formulation of
the type we have developed, which allows us to solve the graph
isomorphism problem in polynomial time, then that very same
formulation -- with minor modifications -- can be used to solve the
Hamilton tour, clique, 3-dimensional matching and any other
subgraph isomorphism problem in polynomial time as well. 
Everything thus hinges on the graph isomorphism paper.

     * The Tony Mansfield counterexample regarding the
applicability of the Q matrices, with respect to ensuring
isomorphism, is not strictly relevant since the paper was not
designed to address the issue of multigraphs.  After some
electronic dialogue, Tony Mansfield himself has suggested an
elegant way of coping with multigraphs or weighted graphs entirely
within the spirit of the Ta=b constraints.  It is thus possible to
handle directed or undirected graphs, graphs with loops,
multigraphs, weighted graphs and subgraphs -- all within the same
general framework.

     * With respect to the Michael Robson counterexample it needs
to be pointed out that although the example he gives does not have
a C_0 pattern it does have a C_0 sub-pattern since all the vectors
q5 through to q10 and any convex combination of them provide such
C_0 sub-patterns.  An example of this kind does not therefore
invalidate the proper functioning of formulation F4.  Nevertheless,
the existence of solutions of this type necessitate some
modifications to the theorem and/or additions to the formulation. 
There is at least one way of making the necessary changes and we
will be reporting on this in due course.

     We are particularly in the debt of William Naylor for
suggesting that our LP approach using the Q matrices ought to be
taken seriously even if it needs some modification.  We are further
able to report that our experimental checks of formulation F4 have
turned up no cases of failure -- neither with respect to graph
isomorphism nor with respect to Hamiltonicity checking.  Moreover,
we have found that a form of Boolean closure is a very affective
method for reducing the need to resort to actual linear
programming.  We are in the process of creating an improved version
of the isomorphism paper which takes into account all the above
points and will make it available when it is ready.

               .. E.R. Swart  &  S.J. Gismondi ..

---------------------------------------------------------------------

Nicholas R. Swart
Dept. of Elec. and Comp. Engineering
University of Waterloo
Waterloo, Ontario
CANADA
N2L 3G1