13
$\begingroup$

At http://www.dharwadker.org/tevet/isomorphism/, there is a presentation of an algorithm for determining if two graphs are isomorphic. Given a number of shall we say, "interesting" claims by A Dharwadker, I am not inclined to believe it.

In my investigation, I find that the algorithm will definitely produce the correct answer and tell you that two graphs are not isomorphic when in fact that is correct. However, it is not clear that the algorithm will consistently tell you if two graphs are isomorphic when they actually are. The "proof" of their result leaves something to be desired.

However, I am not aware of a counter-example. Before I start writing software to test out the algorithm, I thought I would see if anyone was already aware of a counter-example.

Someone requested a synopsis of the algorithm. I will do what I can here, but to really understand it, you should visit http://www.dharwadker.org/tevet/isomorphism/.

There are two phases to the algorithm: A "signature" phase and a sorting phase. The first "signature" phase (this is my term for their process; they call it generating the "sign matrix") effectively sorts vertices into different equivalence classes. The second phase first orders vertices according to their equivalence class, and then applies a sort procedure within equivalence classes to establish an isomorphism between the two graphs. Interestingly, they do not claim to establish a canonical form for the graphs - instead, one graph is used as a kind of template for the second.

The signature phase is actually quite interesting, and I would not do it justice here by attempting to paraphrase it. If you want further details, I recommend following the link to examine his signature phase. The generated "sign matrix" certainly retains all information about the original graph and then establishes a bit more information. After collecting the signatures, they ignore the original matrix since the signatures contain the entire information about the original matrix. Suffice to say that the signature performs some operation that applies to each edge related to the vertex and then they collects the multiset of elements for a vertex to establish an equivalence class for the vertex.

The second phase - the sort phase - is the part that is dubious. In particular, I would expect that if their process worked, then the algorithm developed by Anna Lubiw for providing a "Doubly Lexical Ordering of Matrices" (See: http://dl.acm.org/citation.cfm?id=22189) would also work to define a canonical form for a graph.

To be fair, I do not entirely understand their sort process, though I think they do a reasonable job of describing it. (I just have not worked through all the details). In other words, I may be missing something. However, it is unclear how this process can do much more than accidentally find an isomorphism. Sure, they will probably find it with high probability, but not with a guarantee. If the two graphs are non-isomorphic, the sort process will never find it, and the process correctly rejects the graphs.

Improve this question
$\endgroup$
17
  • $\begingroup$ Can you give a summary of algorithm's idea? $\endgroup$
    – Mohammad Al-Turkistany
    Commented Aug 11, 2015 at 5:53
  • 1
    $\begingroup$ see also math.stackexchange.com/questions/333633/…. This just shows that there is a good chance to find a counterexample to the provided program, but one still has to find one... $\endgroup$
    – Thomas Klimpel
    Commented Aug 11, 2015 at 23:37
  • $\begingroup$ Strongly regular graphs look like a good bet, but I haven't had any luck with randomly selected permutations of Petersen's graph, Clebsch's graph, or the 4x4 rook's graph. $\endgroup$
    – Peter Taylor
    Commented Aug 12, 2015 at 16:48
  • $\begingroup$ Similarly, I tried the Shrikhande graph, but I did not try all permutations. I e-mailed Anna Lubiw to ask her for counter-examples to her "Doubly Lexical Ordering of Matrices", but she has not responded (at least not yet). I suspect that I will need to do a more systematic search. $\endgroup$
    – Bill Province
    Commented Aug 12, 2015 at 17:18
  • 1
    $\begingroup$ dont feel you are doing a service by omitting extravagant claims of the article although it would certainly likely raise flags on this site. what are their extravagant claims that make you skeptical? maybe they claim it is fast-performing, but that cannot be disproven with a single counterexample. ie/eg its possible the algorithm is correct (havent looked) but the complexity analysis is off. anyway invite further discussion/ deeper analysis in Theoretical Computer Science Chat, where several visitors have expressed significant interest in GI in the past & there is a recent extended discussion. $\endgroup$
    – vzn
    Commented Aug 13, 2015 at 1:58

1 Answer 1

Reset to default
23
$\begingroup$

For graphA.txt:

25
 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0
 1 0 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0
 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1
 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0
 1 1 1 0 0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 1 0 0 1 1 0
 1 1 1 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
 1 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 1
 1 0 0 1 1 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1
 1 0 0 1 0 1 0 1 0 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0 0
 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 1
 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 0 0 1 0
 1 0 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 0
 1 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 0 1
 0 1 0 1 1 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1
 0 1 0 1 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 0 1 1 0 1 0
 0 1 0 1 0 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 1
 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 0 0 0 1 1
 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 1 0 0
 0 1 0 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 0 0 0 1 1 1 0
 0 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 1 0 0 1 1 0 1 0
 0 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0 1 0 0 1 0 1
 0 0 1 1 0 0 1 0 1 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0
 0 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 0 1 1 0 1 1 0 0 1
 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 1
 0 0 1 0 0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 1 0

and graphB.txt:

25
 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 1 1 0 1 0
 0 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 0 0 1
 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0
 1 1 1 0 1 0 1 1 1 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0
 1 1 0 1 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0
 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 1 0 0 1 1 1 1 1
 0 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 0
 0 0 1 1 0 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 1 0 0 0 1
 0 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 1 1
 1 0 0 1 1 1 1 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1
 1 0 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0
 1 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0 1
 1 0 0 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1
 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 0 1 1 1 0
 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0
 1 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 1
 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 1 0 1 0 1 0 0 0 0 0
 1 0 1 0 0 1 1 1 0 1 0 1 0 0 0 0 1 0 1 1 1 0 0 1 0
 1 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 0 1 0 0
 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 1 1 0 0 0 1 0 1 1
 1 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 1
 1 1 0 1 0 1 1 0 0 0 1 1 1 1 0 0 0 0 0 1 0 0 0 1 1
 0 0 1 0 0 1 0 0 1 1 1 1 0 1 1 1 0 0 1 0 0 0 0 1 1
 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 0
 0 1 0 0 0 1 0 1 1 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 0

which is obtained from graphA.txt by applying the (random) permutation

 22 9 24 11 15 8 5 18 13 14 2 10 23 0 3 17 4 16 6 19 7 21 12 1 20

the C++ program isororphism.cpp from Figure 6.3. A C++ program for the graph isomorphism algorithm in http://www.dharwadker.org/tevet/isomorphism/ delivers the following output:

The Graph Isomorphism Algorithm
by Ashay Dharwadker and John-Tagore Tevet
http://www.dharwadker.org/tevet/isomorphism/
Copyright (c) 2009
Computing the Sign Matrix of Graph A...
Computing the Sign Matrix of Graph B...
Graph A and Graph B have the same sign frequency vectors in lexicographic order but cannot be isomorphic.
See result.txt for details.

So we may assume that this is a counter-example to the Dharwadker-Tevet Graph Isomorphism algorithm.

As suggested by Bill Province, the problem is

4.1. Proposition. If graphs $G_A$ and $G_B$ are isomorphic, then the algorithm finds an isomorphism.

Bill Province's objection is that the proof of Proposition 4.1. doesn't use any special property of the sign matrix that wouldn't also apply to the adjacency matrix. More precisely, the following step in the proof is wrong:

For the induction hypothesis, assume that rows $1, ..., t$ of $A$ and $B$ have been perfectly matched by Procedure 3.4 such that the vertex labels for the rows $1, ..., t$ of $A$ are $v_1, ..., v_t$ and the vertex labels for the rows $1, ..., t$ of $B$ are $φ(v_1) = v'_1, ..., φ(v_t) = v'_t$ respectively.

because even if the rows have been perfectly matched, it doesn't follow that the vertex labels match the labels given by any isomorphism $φ$.

Because a hole in the correctness proof was identified, the above counter-example should be sufficient for refuting claimed correctness of the proposed algorithm.

Acknowledgments The counter-example is the first of the 8th graph pairs from

http://funkybee.narod.ru/graphs.htm

To manipulate graphs, I used and modified source code from ScrewBoxR1160.tar found at

https://people.mpi-inf.mpg.de/~pascal/software/

To understand the hole in the correctness proof, András Salamon comment about Weisfeiler-Lehman was very helpful, as were the explanations from

http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf

Motivation to use this question as an opportunity to get familiar with nauty/Traces and the practical aspects of graph isomorphism was provided by vzn. The benefit of learning how to use state of the art programs for graph isomorphisms made it worthwhile to sink some time for finding a counter-example (which I strongly believed to exist).

Improve this answer
$\endgroup$
5
  • $\begingroup$ Thank you for the very detailed response. Was there a selection criteria you used for the graph to find the counter-example? Once the counter-example was selected, your comment seems to suggest that the permutation was chosen randomly. Was this true? Or was there more to the selection of the permutation? $\endgroup$
    – Bill Province
    Commented Aug 16, 2015 at 18:22
  • $\begingroup$ @BillProvince The selection criteria was based on the comment by András Salamon, because it indicated that a Cai, Fürer and Immerman construction might be successful. I first tried an n=546 example from Pascal Schweitzer, but the original C++ program isororphism.cpp is now computing since > 1566 minutes. I used better data structures and learned after > 2h that the big counter-example works. I knew that trg787/funkybee had some Cai, Fürer and Immerman constructions among his graph pairs, so I tried my luck. I tried multiple random permutations (for the n=25 example), the second one worked. $\endgroup$
    – Thomas Klimpel
    Commented Aug 16, 2015 at 18:47
  • $\begingroup$ which one is time saving , 1. finding a counter example 2. proving 4.1 is wrong . $\endgroup$
    – Michael
    Commented Aug 18, 2015 at 9:27
  • $\begingroup$ I stopped the original C++ program isoromorphism.cpp for the n = 546 example now, after running for more than 6200 minutes with no end in sight. $\endgroup$
    – Thomas Klimpel
    Commented Aug 20, 2015 at 0:33
  • $\begingroup$ @ThomasKlimpel I plan on writing a paper that mentions this result. If you have a preferred professional attribution, you can e-mail me that attribution at [email protected]. Regardless, I intend to follow the attribution requirements posted at blog.stackexchange.com/2009/06/attribution-required. $\endgroup$
    – Bill Province
    Commented Aug 21, 2015 at 23:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.