<blockquote>
  <p>I wanted to know whether the community is aware of Troﬁmov's results, and whether it's been proved, refuted, or unresolved?</p>
</blockquote>

<p>I tested it (<strong>MT2GI-1.4.2</strong>), just now.<br>
It proved to be a soap bubble: it happily <strong>failed</strong> to detect GI for this pair of <strong>isomorphic</strong><br>
Ramsey graphs:</p>

<p>1-2,1-3,1-5,1-9,1-10,1-14,1-16,1-17,2-3,2-4,2-6,2-10,2-11,2-15,2-17,3-4,3-5,3-7,3-11,3-12,3-16,4-5,4-6,4-8,4-12,4-13,4-17,5-6,5-7,5-9,5-13,5-14,6-7,6-8,6-10,6-14,6-15,7-8,7-9,7-11,7-15,7-16,8-9,8-10,8-12,8-16,8-17,9-10,9-11,9-13,9-17,10-11,10-12,10-14,11-12,11-13,11-15,12-13,12-14,12-16,13-14,13-15,13-17,14-15,14-16,15-16,15-17,16-17</p>

<p><strong>and</strong></p>

<p>1-6,1-8,1-9,1-11,1-13,1-14,1-15,1-16,2-3,2-4,2-5,2-8,2-12,2-13,2-15,2-16,3-5,3-6,3-7,3-11,3-12,3-14,3-15,4-5,4-6,4-8,4-9,4-10,4-15,4-17,5-9,5-10,5-11,5-14,5-16,6-7,6-8,6-10,6-14,6-15,7-8,7-10,7-11,7-12,7-16,7-17,8-9,8-12,8-16,9-11,9-12,9-14,9-17,10-13,10-14,10-16,10-17,11-15,11-16,11-17,12-13,12-14,12-17,13-14,13-15,13-16,13-17,15-17</p>

<p>PS<br>
<strong>Their adjacency matrices are:</strong></p>

<p>17<br>
0 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1<br>
1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1<br>
1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 0<br>
0 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1<br>
1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0<br>
0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 0<br>
0 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0<br>
0 0 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1<br>
1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 0 1<br>
1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 0<br>
0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0<br>
0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0<br>
0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1<br>
1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0<br>
0 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1<br>
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1<br>
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0  </p>

<p><strong>and</strong></p>

<p>17<br>
0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0<br>
0 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0<br>
0 1 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0<br>
0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1<br>
0 1 1 1 0 0 0 0 1 1 1 0 0 1 0 1 0<br>
1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0<br>
0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1 1<br>
1 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0<br>
1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1<br>
0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 1 1<br>
1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 1 1<br>
0 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1<br>
1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1<br>
1 0 1 0 1 1 0 0 1 1 0 1 1 0 0 0 0<br>
1 1 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1<br>
1 1 0 0 1 0 1 1 0 1 1 0 1 0 0 0 0<br>
0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 0  </p>

<p>PPS<br>
<strong>For the sake of completeness,<br>
this is yesterday's screenshot of failed MT2GI-1.4.2:</strong><br>
<a href="http://savepic.net/952853.jpg">http://savepic.net/952853.jpg</a></p>

<p><strong>PPPS</strong><br>
It is left to refute my own algorithm.<br>
I wrote very short but very clear and understandable<br>
description of it: <a href="http://funkybee.narod.ru/griso.htm">http://funkybee.narod.ru/griso.htm</a><br>
C++ code for the algo and sample graphs included.  </p>

<p><strong>PS#4</strong><br>
Very interesting to see what does my function foo() return for these two<br>
<strong>NON</strong> isomorphic Praust graphs: <a href="http://funkybee.narod.ru/griso_praust.htm">http://funkybee.narod.ru/griso_praust.htm</a><br>
20 rows in red are <strong>not</strong> equal. Accidentally ( <strong>???</strong> ) it's <strong>the first</strong> rows of the 2D vectors.  </p>

<p><strong>PS#5</strong><br>
... and 2 <strong>NON</strong> isomorphic Siberian graphs: <a href="http://funkybee.narod.ru/griso_siberian.htm">http://funkybee.narod.ru/griso_siberian.htm</a><br>
This time the rows-in-red are from row #241 to the end (row #780). Also note that each 2<br>
not equal rows (the left and the right) differentiate only at their very ends - when<br>
two <strong>bfs waves</strong> meet each other.</p>

CC BY-SA 2.5
2011-04-04T18:22:15.560Z
Nice. This is Paley(17), right? Is the second copy just a random permutation or did you do anything tricky to construct it?
David Eppstein
CC BY-SA 2.5
2011-04-04T18:31:47.533Z
Sorry, David. I can't say for sure. This pair of graphs I borrowed from this article: http://www.dharwadker.org/tevet/isomorphism/
trg787
CC BY-SA 2.5
2011-04-04T19:20:47.447Z
@David ;; David, I see you are an expert. Could you be so kind, in your some spare time, to check my utility for GI testing? It's at http://sourceforge.net/projects/griso It's in C++, very simple, easy to compile, easy to run. And it's... polynomial-time and due to this it's very fast (refuting its algorithm would be a great result for me). Btw on Siberian graphs MT2GI-1.4.2 ran for ~60(s) - too slow to my taste.
trg787
CC BY-SA 3.0
2011-04-18T08:36:14.133Z
Wow. That was the best TCS drama that I've read since the Deolalikar episode.
Huck Bennett
CC BY-SA 2.5
2011-04-04T17:35:11.740Z
2011-04-07T07:13:17.890Z
2011-04-07T07:13:17.890Z
trg787
<p>This is software bug only. For FP implementation we have right result:</p>

<p>MT2GI v 1.4.2.beta</p>

<blockquote>
  <blockquote>
    <p>Algorithm 1 FP (implementation via floating points usage; fast, but may have rounding errors)
    Input:
    Graph 1:
    1-2,1-3,1-5,1-9,1-10,1-14,1-16,1-17,2-3,2-4,2-6,2-10,2-11,2-15,2-17,3-4,3-5,3-7,3-11,
    3-12,3-16,4-5,4-6,4-8,4-12,4-13,4-17,5-6,5-7,5-9,5-13,5-14,6-7,6-8,6-10,6-14,6-15,7-8,
    7-9,7-11,7-15,7-16,8-9,8-10,8-12,8-16,8-17,9-10,9-11,9-13,9-17,10-11,10-12,10-14,11-12,
    11-13,11-15,12-13,12-14,12-16,13-14,13-15,13-17,14-15,14-16,15-16,15-17,16-17
    Graph 2:
    1-6,1-8,1-9,1-11,1-13,1-14,1-15,1-16,2-3,2-4,2-5,2-8,2-12,2-13,2-15,2-16,3-5,3-6,3-7,
    3-11,3-12,3-14,3-15,4-5,4-6,4-8,4-9,4-10,4-15,4-17,5-9,5-10,5-11,5-14,5-16,6-7,6-8,6-10,
    6-14,6-15,7-8,7-10,7-11,7-12,7-16,7-17,8-9,8-12,8-16,9-11,9-12,9-14,9-17,10-13,10-14,
    10-16,10-17,11-15,11-16,11-17,12-13,12-14,12-17,13-14,13-15,13-16,13-17,15-17
    Number of vertices is 17
    Number of edges is 68
    GI test: started 15.04.2011 16:50:51
    GI found:
    1-1, 2-13, 3-16, 4-2, 5-8, 6-12, 7-7, 8-3, 9-6, 10-14, 11-10, 12-5, 13-4, 14-9, 15-17, 
    16-11, 17-15,
    GI test: finished 15.04.2011 16:50:51
    Time is 0 sec.
    DebugFlag=0
    End -------------------------------</p>
  </blockquote>
</blockquote>

<p>So, rational number library has a bug. There is email in the paper. So be sure to drop me email if and when you find a bug. The paper was discussed in many Internet forums and I have no time to find such discussions via google. The fact is that nobody found any fatal error in the proof. The objective of this work seems rather theoretical than practical. The program was made for better understanding of suggested approach not more.</p>

CC BY-SA 3.0
2011-04-17T13:36:06.460Z
PS Note, in Sep. 21, 2010 the paper was updated: http://arxiv.org/abs/1004.1808
MT2
CC BY-SA 3.0
2011-04-17T16:52:57.093Z
From my profanic point of view all attempts to prove it (GI in P) via numericals/linear algebra will inevitably fail. For decades people keep on chewing the same ideas, with slight ("crucial", as they imagine, wishfully) variations.
trg787
CC BY-SA 3.0
2011-04-17T18:20:42.643Z
Sorry, but I am not "Misha" for you. Please, be polite. And, please, give arguments for your statements "A "BUG" proves erhhh..." (what does it mean?), "all attempts to prove it (GI in P) via numericals/linear algebra will inevitably fail". Recently, someone (nic name "upsetter") wrote similar message about Paley-17 in Russian forum dxdy.ru. Moderator asked him about correct way for discussion. Are you "upsetter"?
MT2
CC BY-SA 3.0
2011-04-18T07:35:33.187Z
Please remain nice and professional. We are considering the situation about this question on the meta. You can read and contribute to the discussion by following [this link](http://meta.cstheory.stackexchange.com/questions/1110/discussions-on-errors-in-papers).
Kaveh
CC BY-SA 3.0
2011-04-18T10:26:35.303Z
@MT2: I must admit I downvoted without leaving a comment, which is considered bad practice, so let me explain my downvote. I have not read your paper, and so do not have any particular informed opinion as to its correctness, and my vote was not intended to be a judgement of correctness of your comment. I simply downvoted because your answer essentially reduces to saying that there is a bug in the code (which is essentially impossible for any of us to verify) without showing why you expect the other result to be correct. (continued below).
Joe Fitzsimons
CC BY-SA 3.0
2011-04-18T10:30:08.390Z
(continued) Also, you did not really deal with anything that David brought up above. So the reason I downvoted was simply because I didn't think the answer particularly fit the current state of the question (+ accepted answer).
Joe Fitzsimons
CC BY-SA 3.0
2011-04-18T12:23:15.050Z
Joe Fitzsimons: 1)"without showing why you expect the other result to be correct" - the line "GI found:" shows it! 2) What questions David brought up above? What errors he found in my paper? He only said a few common words about algorithms for graph isomorphism. I see nothing useful for discussion in these his words :-(
MT2
CC BY-SA 3.0
2011-04-18T16:52:57.473Z
@MT2: as regards (1) showing that the program now outputs the correct result is in no way a proof that the calculation it used to obtain that result is any more valid than that used to obtain the prior incorrect result. Explaining what exactly the software bug was, and how it caused the divergence, would be far more convincing. As regards (2), I was refering to the discussion he pointed to. That said, I have to agree with what others have said on meta that this is not an appropriate place to discuss issues of correctness of unpublished work, so I apologise for bringing it up.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-18T16:55:23.463Z
@MT2: As I have already said, my intention is not to express any opinion as to the correctness of your work. I was simply trying to explain my down-vote, and to distance it from @trg787's comments.
Joe Fitzsimons
CC BY-SA 3.0
2011-04-18T21:07:34.990Z
Joe Fitzsimons: trg787 used the mode RN (which uses rational number library), I used mode FP (which does not use the library) for the same algorithm. Obviously the library has a bug. So I do not understand your down-vote.
MT2
CC BY-SA 3.0
2011-04-28T02:25:02.400Z
"Explaining what exactly the software bug was, and how it caused the divergence, would be far more convincing." Impossible to put it better than this.
trg787
CC BY-SA 3.0
2011-04-28T03:16:22.977Z
"trg787 used the mode RN" :)
trg787
CC BY-SA 3.0
2011-04-28T03:42:41.383Z
Eduard Vatutin (the author of Russian page in Wiki on the GIp) tested it against all graphs with num of vertices <= 5
trg787
CC BY-SA 3.0
2011-04-17T13:15:23.910Z
2011-04-17T13:15:23.910Z
MT2
<p>For some more discussion of this particular paper, see <a href="http://en.wikipedia.org/wiki/Talk%3aGraph_isomorphism#Complexity">this thread</a> on a related Wikipedia talk page. Some of the participants in that discussion found specific bugs, and the paper does not seem to have been updated in response. I tried to read it myself but rather than finding any specific bugs I just got lost in vague descriptions of matrices and matrix manipulations that did not make clear which variables were inputs and which were outputs. Based on that experience I don't think the paper should be taken seriously until it's passed some level of peer review (accepted to one of the usual journals or conferences).</p>

<p>More generally, it is easy to define algorithms for graph isomorphism that attempt to amplify some sort of subtle asymmetry in the graph to the point where it is obvious how to match the vertices to each other, and it is hard to find counterexamples for these algorithms, but that is very difficult from having a clear proof of correctness that works for all graphs.</p>

CC BY-SA 2.5
2010-09-07T22:40:38.577Z
just for curiosity, is there a polynomial time (or maybe sublinear) "tester" for general graph isomorphism? when I say tester I mean "property testing algorithm".
Marcos Villagra
CC BY-SA 2.5
2010-09-07T23:04:21.960Z
http://portal.acm.org/citation.cfm?id=1109591
Suresh Venkat
CC BY-SA 2.5
2010-09-08T01:17:28.353Z
@Suresh: If I am not mistaken, the running time of that tester is not polynomial (quasi-polynomial in the two-sided-error algorithm and exponential in the one-sided-error algorithm).  To quote from the paper: “To our knowledge, the best known algorithm for deciding this promise problem in the classical sense (i.e., given two graphs, distinguish whether they are isomorphic or ε-far from being isomorphic) requires quasi-polynomial running time [6].”  Journal version: http://dx.doi.org/10.1137/070680795
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-07T21:34:08.630Z
2010-09-07T21:34:08.630Z
David Eppstein
<p>"Michael I. Troﬁmov" claims that he has found a poly-time algorithm for graph isomorphism, which works for <strong>all</strong> graphs.</p>

<p>The paper is given in <a href="http://arxiv.org/abs/1004.1808v1">arXiv</a>. The <a href="http://mt2.comtv.ru/">companion website</a> gives a proof-of-concept program which runs the algorithm. (The password for the program is given in the paper.)</p>

<p>I wanted to know whether the community is aware of Troﬁmov's results, and whether it's been proved, refuted, or unresolved?</p>

CC BY-SA 3.0
2011-04-18T06:52:26.360Z
I am locking this question for the time being since this is turning into a discussion and until we decide what we should do about it. Note that this question was asked before we decided to forbid [general questions about correctness of preprints](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics/281#281). Please refer to [this meta post](http://meta.cstheory.stackexchange.com/questions/1110/discussions-on-errors-in-papers) for further discussion about this question.
Kaveh
CC BY-SA 2.5
2010-09-07T21:03:29.930Z
Are this kind of discussions on-topic here? I think there are too many claims of P = NP, P ≠ NP, etc. in ArXiv and elsewhere.
Jukka Suomela
CC BY-SA 2.5
2010-09-07T21:36:47.937Z
I agree that there are too many claims, but I think it's helpful to have somewhere public to discuss which of them are worth taking seriously.
David Eppstein
CC BY-SA 2.5
2010-09-07T22:45:17.453Z
Related meta discussion: http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics
Jukka Suomela
<cc.complexity-theory><graph-theory><graph-isomorphism><ds.algorithms>
Polynomial Time Algorithm for Graph Isomorphism Testing
Sadeq Dousti
# Polynomial Time Algorithm for Graph Isomorphism Testing

(Asked by: username_0 on 2010-09-07)

"Michael I. Troﬁmov" claims that he has found a poly-time algorithm for graph isomorphism, which works for **all** graphs.

The paper is given in [arXiv](http://arxiv.org/abs/1004.1808v1). The [companion website](http://mt2.comtv.ru/) gives a proof-of-concept program which runs the algorithm. (The password for the program is given in the paper.)

I wanted to know whether the community is aware of Troﬁmov's results, and whether it's been proved, refuted, or unresolved?

**Tags:** cc.complexity-theory, graph-theory, graph-isomorphism, ds.algorithms

> **Comments:**
> **username_2**: Are this kind of discussions on-topic here? I think there are too many claims of P = NP, P ≠ NP, etc. in ArXiv and elsewhere.  
> **username_3**: I agree that there are too many claims, but I think it's helpful to have somewhere public to discuss which of them are worth taking seriously.  
> **username_2**: Related meta discussion: http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics  
> **username_1**: I am locking this question for the time being since this is turning into a discussion and until we decide what we should do about it. Note that this question was asked before we decided to forbid [general questions about correctness of preprints](http://meta.cstheory.stackexchange.com/questions/274/is-it-ok-to-ask-about-the-correctness-of-preprints-on-crank-friendly-topics/281#281). Please refer to [this meta post](http://meta.cstheory.stackexchange.com/questions/1110/discussions-on-errors-in-papers) for further discussion about this question.  

---

## 3 answers

### Answer by username_3 on 2010-09-07. Score: 29 | Accepted answer

For some more discussion of this particular paper, see [this thread](http://en.wikipedia.org/wiki/Talk%3aGraph_isomorphism#Complexity) on a related Wikipedia talk page. Some of the participants in that discussion found specific bugs, and the paper does not seem to have been updated in response. I tried to read it myself but rather than finding any specific bugs I just got lost in vague descriptions of matrices and matrix manipulations that did not make clear which variables were inputs and which were outputs. Based on that experience I don't think the paper should be taken seriously until it's passed some level of peer review (accepted to one of the usual journals or conferences).

More generally, it is easy to define algorithms for graph isomorphism that attempt to amplify some sort of subtle asymmetry in the graph to the point where it is obvious how to match the vertices to each other, and it is hard to find counterexamples for these algorithms, but that is very difficult from having a clear proof of correctness that works for all graphs.

> **Comments:**
> **username_8**: just for curiosity, is there a polynomial time (or maybe sublinear) "tester" for general graph isomorphism? when I say tester I mean "property testing algorithm".  
> **username_9**: http://portal.acm.org/citation.cfm?id=1109591  
> **username_10**: @Suresh: If I am not mistaken, the running time of that tester is not polynomial (quasi-polynomial in the two-sided-error algorithm and exponential in the one-sided-error algorithm).  To quote from the paper: “To our knowledge, the best known algorithm for deciding this promise problem in the classical sense (i.e., given two graphs, distinguish whether they are isomorphic or ε-far from being isomorphic) requires quasi-polynomial running time [6].”  Journal version: http://dx.doi.org/10.1137/070680795  

---

### Answer by username_4 on 2011-04-04. Score: 23

> I wanted to know whether the community is aware of Troﬁmov's results, and whether it's been proved, refuted, or unresolved?

I tested it (**username_6GI-1.4.2**), just now.  
It proved to be a soap bubble: it happily **failed** to detect GI for this pair of **isomorphic**  
Ramsey graphs:

1-2,1-3,1-5,1-9,1-10,1-14,1-16,1-17,2-3,2-4,2-6,2-10,2-11,2-15,2-17,3-4,3-5,3-7,3-11,3-12,3-16,4-5,4-6,4-8,4-12,4-13,4-17,5-6,5-7,5-9,5-13,5-14,6-7,6-8,6-10,6-14,6-15,7-8,7-9,7-11,7-15,7-16,8-9,8-10,8-12,8-16,8-17,9-10,9-11,9-13,9-17,10-11,10-12,10-14,11-12,11-13,11-15,12-13,12-14,12-16,13-14,13-15,13-17,14-15,14-16,15-16,15-17,16-17

**and**

1-6,1-8,1-9,1-11,1-13,1-14,1-15,1-16,2-3,2-4,2-5,2-8,2-12,2-13,2-15,2-16,3-5,3-6,3-7,3-11,3-12,3-14,3-15,4-5,4-6,4-8,4-9,4-10,4-15,4-17,5-9,5-10,5-11,5-14,5-16,6-7,6-8,6-10,6-14,6-15,7-8,7-10,7-11,7-12,7-16,7-17,8-9,8-12,8-16,9-11,9-12,9-14,9-17,10-13,10-14,10-16,10-17,11-15,11-16,11-17,12-13,12-14,12-17,13-14,13-15,13-16,13-17,15-17

PS  
**Their adjacency matrices are:**

17  
0 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1  
1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 0 1  
1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1 0  
0 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0 1  
1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 0 0  
0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0 0  
0 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1 0  
0 0 0 1 0 1 1 0 1 1 0 1 0 0 0 1 1  
1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 0 1  
1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 0  
0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0  
0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1 0  
0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0 1  
1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1 0  
0 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1 1  
1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0 1  
1 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 0

**and**

17  
0 0 0 0 0 1 0 1 1 0 1 0 1 1 1 1 0  
0 0 1 1 1 0 0 1 0 0 0 1 1 0 1 1 0  
0 1 0 0 1 1 1 0 0 0 1 1 0 1 1 0 0  
0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 0 1  
0 1 1 1 0 0 0 0 1 1 1 0 0 1 0 1 0  
1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 0  
0 0 1 0 0 1 0 1 0 1 1 1 0 0 0 1 1  
1 1 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0  
1 0 0 1 1 0 0 1 0 0 1 1 0 1 0 0 1  
0 0 0 1 1 1 1 0 0 0 0 0 1 1 0 1 1  
1 0 1 0 1 0 1 0 1 0 0 0 0 0 1 1 1  
0 1 1 0 0 0 1 1 1 0 0 0 1 1 0 0 1  
1 1 0 0 0 0 0 0 0 1 0 1 0 1 1 1 1  
1 0 1 0 1 1 0 0 1 1 0 1 1 0 0 0 0  
1 1 1 1 0 1 0 0 0 0 1 0 1 0 0 0 1  
1 1 0 0 1 0 1 1 0 1 1 0 1 0 0 0 0  
0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 0 0

PPS  
**For the sake of completeness,  
this is yesterday's screenshot of failed username_6GI-1.4.2:**  
<http://savepic.net/952853.jpg>

**PPPS**  
It is left to refute my own algorithm.  
I wrote very short but very clear and understandable  
description of it: <http://funkybee.narod.ru/griso.htm>  
C++ code for the algo and sample graphs included.

**PS#4**  
Very interesting to see what does my function foo() return for these two  
**NON** isomorphic Praust graphs: <http://funkybee.narod.ru/griso_praust.htm>  
20 rows in red are **not** equal. Accidentally ( **???** ) it's **the first** rows of the 2D vectors.

**PS#5**  
... and 2 **NON** isomorphic Siberian graphs: <http://funkybee.narod.ru/griso_siberian.htm>  
This time the rows-in-red are from row #241 to the end (row #780). Also note that each 2  
not equal rows (the left and the right) differentiate only at their very ends - when  
two **bfs waves** meet each other.

> **Comments:**
> **username_3**: Nice. This is Paley(17), right? Is the second copy just a random permutation or did you do anything tricky to construct it?  
> **username_4**: Sorry, David. I can't say for sure. This pair of graphs I borrowed from this article: http://www.dharwadker.org/tevet/isomorphism/  
> **username_4**: @David ;; David, I see you are an expert. Could you be so kind, in your some spare time, to check my utility for GI testing? It's at http://sourceforge.net/projects/griso It's in C++, very simple, easy to compile, easy to run. And it's... polynomial-time and due to this it's very fast (refuting its algorithm would be a great result for me). Btw on Siberian graphs username_6GI-1.4.2 ran for ~60(s) - too slow to my taste.  
> **username_5**: Wow. That was the best TCS drama that I've read since the Deolalikar episode.  

---

### Answer by username_6 on 2011-04-17. Score: -6

This is software bug only. For FP implementation we have right result:

username_6GI v 1.4.2.beta

> > Algorithm 1 FP (implementation via floating points usage; fast, but may have rounding errors)
> > Input:
> > Graph 1:
> > 1-2,1-3,1-5,1-9,1-10,1-14,1-16,1-17,2-3,2-4,2-6,2-10,2-11,2-15,2-17,3-4,3-5,3-7,3-11,
> > 3-12,3-16,4-5,4-6,4-8,4-12,4-13,4-17,5-6,5-7,5-9,5-13,5-14,6-7,6-8,6-10,6-14,6-15,7-8,
> > 7-9,7-11,7-15,7-16,8-9,8-10,8-12,8-16,8-17,9-10,9-11,9-13,9-17,10-11,10-12,10-14,11-12,
> > 11-13,11-15,12-13,12-14,12-16,13-14,13-15,13-17,14-15,14-16,15-16,15-17,16-17
> > Graph 2:
> > 1-6,1-8,1-9,1-11,1-13,1-14,1-15,1-16,2-3,2-4,2-5,2-8,2-12,2-13,2-15,2-16,3-5,3-6,3-7,
> > 3-11,3-12,3-14,3-15,4-5,4-6,4-8,4-9,4-10,4-15,4-17,5-9,5-10,5-11,5-14,5-16,6-7,6-8,6-10,
> > 6-14,6-15,7-8,7-10,7-11,7-12,7-16,7-17,8-9,8-12,8-16,9-11,9-12,9-14,9-17,10-13,10-14,
> > 10-16,10-17,11-15,11-16,11-17,12-13,12-14,12-17,13-14,13-15,13-16,13-17,15-17
> > Number of vertices is 17
> > Number of edges is 68
> > GI test: started 15.04.2011 16:50:51
> > GI found:
> > 1-1, 2-13, 3-16, 4-2, 5-8, 6-12, 7-7, 8-3, 9-6, 10-14, 11-10, 12-5, 13-4, 14-9, 15-17,
> > 16-11, 17-15,
> > GI test: finished 15.04.2011 16:50:51
> > Time is 0 sec.
> > DebugFlag=0
> > End -------------------------------

So, rational number library has a bug. There is email in the paper. So be sure to drop me email if and when you find a bug. The paper was discussed in many Internet forums and I have no time to find such discussions via google. The fact is that nobody found any fatal error in the proof. The objective of this work seems rather theoretical than practical. The program was made for better understanding of suggested approach not more.

> **Comments:**
> **username_6**: PS Note, in Sep. 21, 2010 the paper was updated: http://arxiv.org/abs/1004.1808  
> **username_4**: From my profanic point of view all attempts to prove it (GI in P) via numericals/linear algebra will inevitably fail. For decades people keep on chewing the same ideas, with slight ("crucial", as they imagine, wishfully) variations.  
> **username_6**: Sorry, but I am not "Misha" for you. Please, be polite. And, please, give arguments for your statements "A "BUG" proves erhhh..." (what does it mean?), "all attempts to prove it (GI in P) via numericals/linear algebra will inevitably fail". Recently, someone (nic name "upsetter") wrote similar message about Paley-17 in Russian forum dxdy.ru. Moderator asked him about correct way for discussion. Are you "upsetter"?  
> **username_1**: Please remain nice and professional. We are considering the situation about this question on the meta. You can read and contribute to the discussion by following [this link](http://meta.cstheory.stackexchange.com/questions/1110/discussions-on-errors-in-papers).  
> **username_7**: @username_6: I must admit I downvoted without leaving a comment, which is considered bad practice, so let me explain my downvote. I have not read your paper, and so do not have any particular informed opinion as to its correctness, and my vote was not intended to be a judgement of correctness of your comment. I simply downvoted because your answer essentially reduces to saying that there is a bug in the code (which is essentially impossible for any of us to verify) without showing why you expect the other result to be correct. (continued below).  
> **username_7**: (continued) Also, you did not really deal with anything that David brought up above. So the reason I downvoted was simply because I didn't think the answer particularly fit the current state of the question (+ accepted answer).  
> **username_6**: username_7: 1)"without showing why you expect the other result to be correct" - the line "GI found:" shows it! 2) What questions David brought up above? What errors he found in my paper? He only said a few common words about algorithms for graph isomorphism. I see nothing useful for discussion in these his words :-(  
> **username_7**: @username_6: as regards (1) showing that the program now outputs the correct result is in no way a proof that the calculation it used to obtain that result is any more valid than that used to obtain the prior incorrect result. Explaining what exactly the software bug was, and how it caused the divergence, would be far more convincing. As regards (2), I was refering to the discussion he pointed to. That said, I have to agree with what others have said on meta that this is not an appropriate place to discuss issues of correctness of unpublished work, so I apologise for bringing it up.  
> **username_7**: @username_6: As I have already said, my intention is not to express any opinion as to the correctness of your work. I was simply trying to explain my down-vote, and to distance it from @username_4's comments.  
> **username_6**: username_7: username_4 used the mode RN (which uses rational number library), I used mode FP (which does not use the library) for the same algorithm. Obviously the library has a bug. So I do not understand your down-vote.  
> **username_4**: "Explaining what exactly the software bug was, and how it caused the divergence, would be far more convincing." Impossible to put it better than this.  
> **username_4**: "username_4 used the mode RN" :)  
> **username_4**: Eduard Vatutin (the author of Russian page in Wiki on the GIp) tested it against all graphs with num of vertices <= 5  

---

