7
$\begingroup$

"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?

Improve this question
$\endgroup$
4
  • 7
    $\begingroup$ 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. $\endgroup$
    – Jukka Suomela
    Sep 7, 2010 at 21:03
  • 14
    $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Sep 7, 2010 at 21:36
  • 2
    $\begingroup$ Related meta discussion: meta.cstheory.stackexchange.com/questions/274/… $\endgroup$
    – Jukka Suomela
    Sep 7, 2010 at 22:45
  • $\begingroup$ 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. Please refer to this meta post for further discussion about this question. $\endgroup$
    – Kaveh
    Apr 18, 2011 at 6:52

3 Answers 3

Reset to default
29
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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". $\endgroup$
    – Marcos Villagra
    Sep 7, 2010 at 22:40
  • 3
    $\begingroup$ portal.acm.org/citation.cfm?id=1109591 $\endgroup$
    – Suresh Venkat
    Sep 7, 2010 at 23:04
  • 2
    $\begingroup$ @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: dx.doi.org/10.1137/070680795 $\endgroup$
    – Tsuyoshi Ito
    Sep 8, 2010 at 1:17
23
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 5
    $\begingroup$ Nice. This is Paley(17), right? Is the second copy just a random permutation or did you do anything tricky to construct it? $\endgroup$
    – David Eppstein
    Apr 4, 2011 at 18:22
  • $\begingroup$ Sorry, David. I can't say for sure. This pair of graphs I borrowed from this article: dharwadker.org/tevet/isomorphism $\endgroup$
    – trg787
    Apr 4, 2011 at 18:31
  • $\begingroup$ @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 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. $\endgroup$
    – trg787
    Apr 4, 2011 at 19:20
  • 5
    $\begingroup$ Wow. That was the best TCS drama that I've read since the Deolalikar episode. $\endgroup$
    – Huck Bennett
    Apr 18, 2011 at 8:36
-6
$\begingroup$

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.

Improve this answer
$\endgroup$
13
  • $\begingroup$ PS Note, in Sep. 21, 2010 the paper was updated: arxiv.org/abs/1004.1808 $\endgroup$
    – MT2
    Apr 17, 2011 at 13:36
  • $\begingroup$ 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. $\endgroup$
    – trg787
    Apr 17, 2011 at 16:52
  • $\begingroup$ 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"? $\endgroup$
    – MT2
    Apr 17, 2011 at 18:20
  • 3
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Apr 18, 2011 at 7:35
  • $\begingroup$ @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). $\endgroup$
    – Joe Fitzsimons
    Apr 18, 2011 at 10:26

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