7

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

The paper is given in arXiv. The companion website 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 Trofimov's results, and whether it's been proved, refuted, or unresolved?

Sadeq Dousti
  • 16,479
  • 9
  • 69
  • 152

3 Answers3

29

For some more discussion of this particular paper, see this thread 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.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • 1
    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 Sep 07 '10 at 22:40
  • 3
    http://portal.acm.org/citation.cfm?id=1109591 – Suresh Venkat Sep 07 '10 at 23:04
  • 2
    @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 Sep 08 '10 at 01:17
23

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

I tested it (MT2GI-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 MT2GI-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.

trg787
  • 479
  • 4
  • 11
  • 5
    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 Apr 04 '11 at 18:22
  • Sorry, David. I can't say for sure. This pair of graphs I borrowed from this article: http://www.dharwadker.org/tevet/isomorphism/ – trg787 Apr 04 '11 at 18:31
  • @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 Apr 04 '11 at 19:20
  • 5
    Wow. That was the best TCS drama that I've read since the Deolalikar episode. – Huck Bennett Apr 18 '11 at 08:36
-6

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

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

MT2
  • 1
  • PS Note, in Sep. 21, 2010 the paper was updated: http://arxiv.org/abs/1004.1808 – MT2 Apr 17 '11 at 13:36
  • 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 Apr 17 '11 at 16:52
  • 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 Apr 17 '11 at 18:20
  • 3
    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. – Kaveh Apr 18 '11 at 07:35
  • @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 Apr 18 '11 at 10:26
  • (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 Apr 18 '11 at 10:30
  • 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 Apr 18 '11 at 12:23
  • @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 Apr 18 '11 at 16:52
  • @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 Apr 18 '11 at 16:55
  • 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 Apr 18 '11 at 21:07
  • "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 Apr 28 '11 at 02:25
  • "trg787 used the mode RN" :) – trg787 Apr 28 '11 at 03:16
  • Eduard Vatutin (the author of Russian page in Wiki on the GIp) tested it against all graphs with num of vertices <= 5 – trg787 Apr 28 '11 at 03:42