home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / theory / 2820 < prev    next >
Encoding:
Internet Message Format  |  1993-01-07  |  3.3 KB
  1. Path: sparky!uunet!think.com!rpi!gatech!concert!borg.cs.unc.edu!not-for-mail
  2. From: plaisted@cs.unc.edu (David Plaisted)
  3. Newsgroups: comp.theory
  4. Subject: Gismondi and Swart's algorithm
  5. Date: 7 Jan 1993 13:08:21 -0500
  6. Organization: The University of North Carolina at Chapel Hill
  7. Lines: 56
  8. Distribution: inet
  9. Message-ID: <1ihrilINNejp@plaisted.cs.unc.edu>
  10. NNTP-Posting-Host: plaisted.cs.unc.edu
  11. Keywords: Graph isomorphism
  12.  
  13.  
  14. Here is a possible counterexample to Gismondi and Swart's algorithm
  15. for graph isomorphism.
  16.  
  17. We can think of the $s_{a,b}$ as relating the vertices a and b, giving
  18. the degree to which a ``fuzzy isomorphism'' maps a to b.  We can think
  19. of $t_{a,b,c,d} as relating the edge (a,b) of one graph to the edge
  20. (c,d) of the other graph.  It's the degree to which a ``fuzzy
  21. isomorphism'' maps (a,b) to (c,d).  Gismondi and Swart give an
  22. associated linear programming problem in which a number of reasonable
  23. linear inequalities are imposed on these values to try to characterize
  24. isomorphism as closely as possible.
  25.  
  26. Let G1 be a graph consisting of two disjoint cycles of length n.  Let
  27. G2 consist of one cycle of length 2n.  Then, the corresponding linear
  28. programming problem of Gismondi and Swart is solvable with a solution
  29. vector consisting entirely of 0 and .5 values.  Each vertex in G1
  30. corresponds to two vertices in G2 by the fuzzy isomorphism.  Each
  31. vertex in G2 corresponds to two vertices in G1 by this fuzzy
  32. isomorphism.  The idea is that as you go around the long cycle in G2,
  33. you go around each of the short cycles in G1, twice.  Also, it's not
  34. possible to reduce any of the .5 coefficients to 0 without increasing
  35. some 0 coefficient.  Of course, the graphs are not isomorphic.
  36.  
  37. Let H1 consist of disjoint copies of G1 and G2.  Let H2 be isomorphic
  38. to H1.  Consider the linear programming problem corresponding to
  39. showing that H1 is isomorphic to H2.  One possible solution to this is
  40. the true isomorphism.  The other one is obtained by two copies of the
  41. solution for G1 and G2 above.  So the G1 in H1 is related to the G2 in
  42. H2 and the G2 in H1 is related to the G1 in H2.  Let's consider this
  43. second solution.  All its values are 0 and .5.  Furthermore, it does
  44. not cover a permutation, though one exists.  In addition, it is not
  45. possible to reduce any of the .5 values to 0 without increasing some 0
  46. value.
  47.  
  48. We can even make G1 and G2 and H1 and H2 connected, by adding a new
  49. vertex connected to everything else.  Also, by extending this idea,
  50. considerably more complicated counterexamples can be found.
  51.  
  52. I don't see any way that Gismondi and Swart's algorithm can
  53. distinguish between these two cases, though I don't fully understand
  54. their method.  So it seems to me that their approach is wrong and even
  55. the algorithm is incorrect.  Of course, an implementation might happen
  56. to give the right answer because of the solutions it happened to find.
  57. So it seems that their approach cannot be saved except by some
  58. fundamentally new ideas.
  59.  
  60. However, consider the set of pairs (G1, G2) of graphs such that the
  61. associated linear programming problem has a (fractional) solution.
  62. This seems to have a fairly restricted structure.  It also includes
  63. the pairs of isomorphic graphs.  So maybe this linear programming
  64. problem can be used as a preprocessing step for a graph isomorphism
  65. algorithm.
  66.  
  67.     Dave Plaisted
  68.  
  69.