<p>For <code>graphA.txt</code>:</p>

<pre><code>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
</code></pre>

<p>and <code>graphB.txt</code>:</p>

<pre><code>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
</code></pre>

<p>which is obtained from <code>graphA.txt</code> by applying the (random) permutation</p>

<pre><code> 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
</code></pre>

<p>the C++ program <code>isororphism.cpp</code> from <strong>Figure 6.3.</strong> <em>A C++ program for the graph isomorphism algorithm</em> in <a href="http://www.dharwadker.org/tevet/isomorphism/">http://www.dharwadker.org/tevet/isomorphism/</a> delivers the following output:</p>

<pre><code>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.
</code></pre>

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

<p>As suggested by Bill Province, the problem is</p>

<blockquote>
  <p><strong>4.1. Proposition.</strong> If graphs $G_A$ and $G_B$ are isomorphic, then the algorithm finds an isomorphism.</p>
</blockquote>

<p>Bill Province's objection is that the proof of <strong>Proposition 4.1.</strong> 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:</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

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

<hr>

<p><strong>Acknowledgments</strong>
The counter-example is the first of the 8th graph pairs from</p>

<blockquote>
  <p><a href="http://funkybee.narod.ru/graphs.htm">http://funkybee.narod.ru/graphs.htm</a></p>
</blockquote>

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

<blockquote>
  <p><a href="https://people.mpi-inf.mpg.de/~pascal/software/">https://people.mpi-inf.mpg.de/~pascal/software/</a></p>
</blockquote>

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

<blockquote>
  <p><a href="http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf">http://users.cecs.anu.edu.au/~pascal/docs/thesis_pascal_schweitzer.pdf</a></p>
</blockquote>

<p>Motivation to use this question as an opportunity to get familiar with <a href="http://pallini.di.uniroma1.it/">nauty/Traces</a> 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).</p>

CC BY-SA 3.0
2015-08-16T18:22:25.227Z
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?
Bill Province
CC BY-SA 3.0
2015-08-16T18:47:21.920Z
@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.
Thomas Klimpel
CC BY-SA 3.0
2015-08-18T09:27:11.190Z
which one is time saving , 1. finding a counter example 2. proving 4.1 is wrong .
Michael
CC BY-SA 3.0
2015-08-20T00:33:52.777Z
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.
Thomas Klimpel
CC BY-SA 3.0
2015-08-21T23:32:06.013Z
@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 billprovince@gmail.com. Regardless, I intend to follow the attribution requirements posted at https://blog.stackexchange.com/2009/06/attribution-required/.
Bill Province
CC BY-SA 3.0
2015-08-16T09:37:50.840Z
2015-08-16T09:37:50.840Z
Thomas Klimpel
<p>At <a href="http://www.dharwadker.org/tevet/isomorphism/">http://www.dharwadker.org/tevet/isomorphism/</a>, 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.</p>

<p>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.</p>

<p>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.</p>

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

<p>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.</p>

<p>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.</p>

<p>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: <a href="http://dl.acm.org/citation.cfm?id=22189">http://dl.acm.org/citation.cfm?id=22189</a>) would also work to define a canonical form for a graph.</p>

<p>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.</p>

CC BY-SA 3.0
2015-08-11T05:53:16.500Z
Can you give a summary of algorithm's idea?
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-08-11T23:37:08.197Z
see also http://math.stackexchange.com/questions/333633/is-the-clique-algorithm-by-ashay-dharwadker-correct. This just shows that there is a good chance to find a counterexample to the provided program, but one still has to find one...
Thomas Klimpel
CC BY-SA 3.0
2015-08-12T16:48:02.640Z
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.
Peter Taylor
CC BY-SA 3.0
2015-08-12T17:18:14.450Z
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.
Bill Province
CC BY-SA 3.0
2015-08-13T01:58:12.633Z
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 [chat], where several visitors have expressed significant interest in GI in the past & there is a recent extended discussion.
vzn
CC BY-SA 3.0
2015-08-13T15:08:56.853Z
more thoughts. the paper claims a P-time algorithm. afaik/ afaict the general strategy of [graph canonization](https://en.wikipedia.org/wiki/Graph_canonization) for GI is generally thought/ conjectured to be impossible by experts. ie that there do not exist canonical forms for isomorphism detection. the [math.se] question cited above by TK claims a counterexample & has other items on correctness. alas, strictly speaking, question falls under this [site policy](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics)
vzn
CC BY-SA 3.0
2015-08-13T21:34:48.463Z
The description you give sounds like Weisfeiler-Lehman, possibly with some additional tweaks.
András Salamon
CC BY-SA 3.0
2015-08-14T23:00:34.273Z
Right - I expect there to be counterexamples. In fact, I would be extremely surprised if there were not. What I was hoping for was that somebody was already aware of a specific counterexample.
Bill Province
CC BY-SA 3.0
2015-08-18T09:25:17.007Z
This post would surely help Mr. Dharwadker , may be he would come up another idea that works!  but the fact is , he would not know the excellent  volunteer work done by OP and others. Thus this post, goes in vein in some sense !!
Michael
CC BY-SA 3.0
2016-01-23T15:57:50.660Z
in some cases, one cannot really refute incorrect P-time claims with an individual counterexample. it requires construction of a _set_ of counterexamples using some method that finds them and showing the trend is non-P. and this can be a very, very subtle/ "hard" challenge and the history of GI has examples of this. also one might expect that counterexamples do not really follow an algorithmic pattern ie are actually "random-looking." so then its almost required to construct an "adversary algorithm" that finds them.
vzn
CC BY-SA 4.0
2022-05-16T05:23:19.363Z
@ThomasKlimpel, thanks for the references to funkybee. Are you able to confirm that example 29 is actually isomorphic? And do you know if the "+++" indicates isomorphism? (Because I am only confirming #2 to be isomorphic. But, of course, I am less confident about those results than I am about showing that 29 is isomorphic.)
smichr
CC BY-SA 4.0
2022-05-16T09:48:14.893Z
I guess that funkybee used "+++"  to indicate isomorphism (detected by his program). But that is not important. I used only the first of the graphs from example 8 and applied a permutation to it myself (that permutation is given in my answer). You can just apply it yourself to confirm that graphA.txt and graphB.txt are isomorphic. Why do you mention example 29? You can use nauty to check whether it is isomorphic. funkybee's program marked examples 1-5, 33, and 35-36 as isomorphic.
Thomas Klimpel
CC BY-SA 4.0
2022-05-16T18:53:44.420Z
OK, downloaded cywin , gcc, nauty and read the manual on how to do the testing. Following the example in the manual, nauty also reports that the graphs are different. But I can give a permutation of rows and columns for each graph that puts them into the same matrix, so either I have misused nauty or else nauty is not able to show that the two graphs are the same. I sent an email to Brendan and the maintainer of funkybee.
smichr
CC BY-SA 4.0
2022-05-16T20:40:18.617Z
If you tell me your permutation, I can check whether it makes the two graphs from example 29 isomorphic.
Thomas Klimpel
CC BY-SA 4.0
2022-05-16T21:30:38.900Z
My working definition of "isomorphic" is that two adjacency matrices are isomorphic if the one represents a row/column permutation of the other; or, alternatively, if both can be put into the same form through such permutations. The first of the two matrices can be put into a canonical form with the following row/col permutation `[11, 14, 13, 10, 12, 15, 9, 0, 8, 7, 4, 5, 1, 6, 2, 3], [0, 1, 9, 6, 4, 7, 13, 11, 3, 15, 12, 2, 14, 10, 5, 8]` while the second becomes the same with `[15, 14, 13, 12, 11, 10, 9, 8, 7, 0, 6, 5, 4, 1, 3, 2], [0, 1, 2, 15, 3, 14, 4, 13, 12, 7, 8, 10, 11, 5, 9, 6]`.
smichr
CC BY-SA 4.0
2022-05-17T00:37:54.970Z
Unifying the permutations, you can permute rows and columns of the first matrix as follows to get the second matrix: `rows=[7, 6, 3, 2, 1, 5, 4, 8, 0, 9, 15, 12, 10, 13, 14, 11];
cols=[0, 1, 9, 4, 13, 10, 8, 15, 12, 5, 2, 14, 3, 11, 7, 6]`.
smichr
CC BY-SA 4.0
2022-05-17T04:03:56.013Z
@ThomasKlimpel, when I test the n=10 graphs from funkybee with nauty it reports that `h and h' are identical. 0-0 1-7 2-3 3-1 4-5 5-6 6-9 7-2 8-8 9-4`. I am still waiting for approval to the nauty mailing list -- are you able to tell me how to use this to find verify the isomorphic relationship between these two graphs?
smichr
<graph-isomorphism>
Is anyone aware of a counter-example to the Dharwadker-Tevet Graph Isomorphism algorithm?
Bill Province
# Is anyone aware of a counter-example to the Dharwadker-Tevet Graph Isomorphism algorithm?

(Asked by: username_0 on 2015-08-11)

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.

**Tags:** graph-isomorphism
> **Comments:**
> **username_1**: Can you give a summary of algorithm's idea?  
> **username_2**: see also http://math.stackexchange.com/questions/333633/is-the-clique-algorithm-by-ashay-dharwadker-correct. This just shows that there is a good chance to find a counterexample to the provided program, but one still has to find one...  
> **username_3**: 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.  
> **username_0**: 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.  
> **username_4**: 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 [chat], where several visitors have expressed significant interest in GI in the past & there is a recent extended discussion.  
> **username_4**: more thoughts. the paper claims a P-time algorithm. afaik/ afaict the general strategy of [graph canonization](https://en.wikipedia.org/wiki/Graph_canonization) for GI is generally thought/ conjectured to be impossible by experts. ie that there do not exist canonical forms for isomorphism detection. the [math.se] question cited above by TK claims a counterexample & has other items on correctness. alas, strictly speaking, question falls under this [site policy](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics)  
> **username_5**: The description you give sounds like Weisfeiler-Lehman, possibly with some additional tweaks.  
> **username_0**: Right - I expect there to be counterexamples. In fact, I would be extremely surprised if there were not. What I was hoping for was that somebody was already aware of a specific counterexample.  
> **username_6**: This post would surely help Mr. Dharwadker , may be he would come up another idea that works!  but the fact is , he would not know the excellent  volunteer work done by OP and others. Thus this post, goes in vein in some sense !!  
> **username_4**: in some cases, one cannot really refute incorrect P-time claims with an individual counterexample. it requires construction of a _set_ of counterexamples using some method that finds them and showing the trend is non-P. and this can be a very, very subtle/ "hard" challenge and the history of GI has examples of this. also one might expect that counterexamples do not really follow an algorithmic pattern ie are actually "random-looking." so then its almost required to construct an "adversary algorithm" that finds them.  
> **username_7**: @ThomasKlimpel, thanks for the references to funkybee. Are you able to confirm that example 29 is actually isomorphic? And do you know if the "+++" indicates isomorphism? (Because I am only confirming #2 to be isomorphic. But, of course, I am less confident about those results than I am about showing that 29 is isomorphic.)  
> **username_2**: I guess that funkybee used "+++"  to indicate isomorphism (detected by his program). But that is not important. I used only the first of the graphs from example 8 and applied a permutation to it myself (that permutation is given in my answer). You can just apply it yourself to confirm that graphA.txt and graphB.txt are isomorphic. Why do you mention example 29? You can use nauty to check whether it is isomorphic. funkybee's program marked examples 1-5, 33, and 35-36 as isomorphic.  
> **username_7**: OK, downloaded cywin , gcc, nauty and read the manual on how to do the testing. Following the example in the manual, nauty also reports that the graphs are different. But I can give a permutation of rows and columns for each graph that puts them into the same matrix, so either I have misused nauty or else nauty is not able to show that the two graphs are the same. I sent an email to Brendan and the maintainer of funkybee.  
> **username_2**: If you tell me your permutation, I can check whether it makes the two graphs from example 29 isomorphic.  
> **username_7**: My working definition of "isomorphic" is that two adjacency matrices are isomorphic if the one represents a row/column permutation of the other; or, alternatively, if both can be put into the same form through such permutations. The first of the two matrices can be put into a canonical form with the following row/col permutation `[11, 14, 13, 10, 12, 15, 9, 0, 8, 7, 4, 5, 1, 6, 2, 3], [0, 1, 9, 6, 4, 7, 13, 11, 3, 15, 12, 2, 14, 10, 5, 8]` while the second becomes the same with `[15, 14, 13, 12, 11, 10, 9, 8, 7, 0, 6, 5, 4, 1, 3, 2], [0, 1, 2, 15, 3, 14, 4, 13, 12, 7, 8, 10, 11, 5, 9, 6]`.  
> **username_7**: Unifying the permutations, you can permute rows and columns of the first matrix as follows to get the second matrix: `rows=[7, 6, 3, 2, 1, 5, 4, 8, 0, 9, 15, 12, 10, 13, 14, 11]; cols=[0, 1, 9, 4, 13, 10, 8, 15, 12, 5, 2, 14, 3, 11, 7, 6]`.  
> **username_7**: @ThomasKlimpel, when I test the n=10 graphs from funkybee with nauty it reports that `h and h' are identical. 0-0 1-7 2-3 3-1 4-5 5-6 6-9 7-2 8-8 9-4`. I am still waiting for approval to the nauty mailing list -- are you able to tell me how to use this to find verify the isomorphic relationship between these two graphs?  

---

## 1 answers

### Answer by username_2 on 2015-08-16. Score: 23 | Accepted answer

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).

> **Comments:**
> **username_0**: 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?  
> **username_2**: @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.  
> **username_6**: which one is time saving , 1. finding a counter example 2. proving 4.1 is wrong .  
> **username_2**: 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.  
> **username_0**: @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 billprovince@gmail.com. Regardless, I intend to follow the attribution requirements posted at https://blog.stackexchange.com/2009/06/attribution-required/.  

---

