home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / theory / 2756 < prev    next >
Encoding:
Text File  |  1992-12-24  |  4.6 KB  |  97 lines
  1. Newsgroups: comp.theory
  2. Path: sparky!uunet!wupost!cs.utexas.edu!torn!watserv2.uwaterloo.ca!watserv1!phonon.uwaterloo.ca!nrswart
  3. From: nrswart@phonon.uwaterloo.ca (Nicholas R. Swart)
  4. Subject: Update on Graph Isomorphism Proof
  5. Message-ID: <Bzs0KA.8pD@watserv1.uwaterloo.ca>
  6. Sender: news@watserv1.uwaterloo.ca
  7. Organization: University of Waterloo
  8. Date: Thu, 24 Dec 1992 18:26:33 GMT
  9. Lines: 86
  10.  
  11. I'm posting this message for my father:
  12.  
  13. -------------------------------------------------------------------------
  14.  
  15.  
  16.                      Graph Isomorphism et al
  17.  
  18.      Although we have not contributed to the comp.theory discussion
  19. directly, we would like to publicly -- in open forum -- express our
  20. appreciation to all those of you who have provided helpful dialogue
  21. on a one-on-one basis regarding our graph isomorphism and N=1
  22. papers.  It seems appropriate, moreover, to bring you all up to
  23. date as to the current status of these papers.  There are several
  24. aspects of the graph isomorphism paper and its relationship to the
  25. N=1 paper which drew significant attention and the outcome of the
  26. resulting dialogue is as follows:
  27.  
  28.      * Several people pointed out that corollary 1 was not fully
  29. justified and possibly in error.  We are happy to report that all
  30. those who have discussed this point with us are now agreed that it
  31. is not in error and can be justified.  Strictly speaking, however,
  32. it does need an additional lemma concerning the implications of the
  33. Ta=b constraints.  The effect of these constraints is largely
  34. benign in that all that they do is require some of the t[abcd] and
  35. possibly some of the s[ab] variables to be zero.  Any solution to
  36. formulation F3 which has a C_0 pattern or a C_0 sub-pattern, which
  37. avoids these zeroes, thus implies the existence of a Q matrix
  38. solution which likewise avoids these zeroes which, in turn, implies
  39. that the graphs being examined are isomorphic.
  40.  
  41.      * Quite a few people have suggested that even if the graph
  42. isomorphism paper is correct that this does not imply the
  43. correctness of the N=1 paper.  We are happy to report that on this
  44. point as well there is now complete agreement with all those with
  45. whom we have discussed the issue.  If there is an LP formulation of
  46. the type we have developed, which allows us to solve the graph
  47. isomorphism problem in polynomial time, then that very same
  48. formulation -- with minor modifications -- can be used to solve the
  49. Hamilton tour, clique, 3-dimensional matching and any other
  50. subgraph isomorphism problem in polynomial time as well. 
  51. Everything thus hinges on the graph isomorphism paper.
  52.  
  53.      * The Tony Mansfield counterexample regarding the
  54. applicability of the Q matrices, with respect to ensuring
  55. isomorphism, is not strictly relevant since the paper was not
  56. designed to address the issue of multigraphs.  After some
  57. electronic dialogue, Tony Mansfield himself has suggested an
  58. elegant way of coping with multigraphs or weighted graphs entirely
  59. within the spirit of the Ta=b constraints.  It is thus possible to
  60. handle directed or undirected graphs, graphs with loops,
  61. multigraphs, weighted graphs and subgraphs -- all within the same
  62. general framework.
  63.  
  64.      * With respect to the Michael Robson counterexample it needs
  65. to be pointed out that although the example he gives does not have
  66. a C_0 pattern it does have a C_0 sub-pattern since all the vectors
  67. q5 through to q10 and any convex combination of them provide such
  68. C_0 sub-patterns.  An example of this kind does not therefore
  69. invalidate the proper functioning of formulation F4.  Nevertheless,
  70. the existence of solutions of this type necessitate some
  71. modifications to the theorem and/or additions to the formulation. 
  72. There is at least one way of making the necessary changes and we
  73. will be reporting on this in due course.
  74.  
  75.      We are particularly in the debt of William Naylor for
  76. suggesting that our LP approach using the Q matrices ought to be
  77. taken seriously even if it needs some modification.  We are further
  78. able to report that our experimental checks of formulation F4 have
  79. turned up no cases of failure -- neither with respect to graph
  80. isomorphism nor with respect to Hamiltonicity checking.  Moreover,
  81. we have found that a form of Boolean closure is a very affective
  82. method for reducing the need to resort to actual linear
  83. programming.  We are in the process of creating an improved version
  84. of the isomorphism paper which takes into account all the above
  85. points and will make it available when it is ready.
  86.  
  87.                .. E.R. Swart  &  S.J. Gismondi ..
  88.  
  89. ---------------------------------------------------------------------
  90.  
  91. Nicholas R. Swart
  92. Dept. of Elec. and Comp. Engineering
  93. University of Waterloo
  94. Waterloo, Ontario
  95. CANADA
  96. N2L 3G1
  97.