Is anyone aware of a counter-example to the Dharwadker-Tevet Graph Isomorphism algorithm? 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.
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).