13
$\begingroup$

Wikipedia's graph isomorphism problem page would seem to indicate that, no, it has not been solved. However, a friend of mine pointed out A Polynomial Time Algorithm for Graph Isomorphism . I am not sophisticated enough to follow the reasoning in the paper.

I do have my own very rough attempt at a polynomial time algorithm without anything like proof, but I'd like to know whether or not this problem has been successfully tackled before proceeding.

So, is the graph isomorphism problem solved?

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ worthwhile question. wrt cyber peer review, it would be nicer if respondents/ answers actually pointed out specific error(s) in the paper rather than generalities. admittedly caveat however here is what professional scientists think of these types of efforts. arxiv is full of erroneous papers, many on P vs NP but many other semifamous problems attract amateur efforts, eg also the Collatz conjecture, twin primes, Goldbach conjecture, etc. $\endgroup$
    – vzn
    Dec 14, 2014 at 3:25
  • 7
    $\begingroup$ @vzn I don't think there is any point wasting our time on reading papers which are almost surely incorrect and shed no new light on the problem. $\endgroup$
    – Yuval Filmus
    Dec 14, 2014 at 18:26
  • 2
    $\begingroup$ @vzn I don't understand your complaint. D.W.'s answer (posted an hour before your comment) links to a comment that does point out a specific error in the ArXiv paper under discussion. $\endgroup$
    – David Richerby
    Dec 15, 2014 at 19:48
  • 2
    $\begingroup$ @vzn The ArXiv paper contains an error. It's not been revised to fix that error. There is no need for any more peer review. I've no idea what you're saying is second-hand: a counter-example is a counter-example, regardless of whether it was communicated to you by its discoverer or by the drug dealer who hangs out behind that seedy bar out on the highway. $\endgroup$
    – David Richerby
    Dec 15, 2014 at 23:21
  • 1
    $\begingroup$ @vzn Presumably, it wasn't revised because the author couldn't fix the error. Note that ArXiv doesn't permit the withdrawal of manuscripts, even if they turn out to be incorrect. $\endgroup$
    – David Richerby
    Dec 15, 2014 at 23:35

4 Answers 4

Reset to default
24
$\begingroup$

No. That paper appears to be flawed. The flaw was explained in a comment by Tracy Hall on MathOverflow. A follow-up comment claims that the author later realized there is a flaw in his algorithm.

As Yuval explains, it is not uncommon to see attempts from amateurs to solve these problems; they tend to be flawed. When it comes to results on famous open problems (e.g., P vs NP, graph isomorphism, etc.), I recommend looking to published literature in reputable peer-reviewed conferences and journals -- peer review is not perfect, but peer-reviewed papers have a much higher likelihood of being correct.

Improve this answer
$\endgroup$
0
18
$\begingroup$

No, the graph isomorphism problem has not been solved. The paper you link to is from 2007–2008, and hasn't been accepted by the wider scientific community. (If it had been, I would have known about it.)

Graph isomorphism, like many other famous problems, attracts many attempts by amateurs. They are almost always wrong. I would advise against trying to tackle this problem without first becoming competent in research-level mathematics.

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ another way to deal with these types of claims by experts is impossibility or barrier results. then a more informative refutation goes in the form "the paper uses an [x] type of argument to try to solve the isomorphism problem, but it is known from [a,b,c] research that there is a specific barrier to this type of approach, and the paper seems unaware of this barrier or reveal specifically how it is overcome." there are results known about this for the isomorphism problem & other key problems eg P vs NP. $\endgroup$
    – vzn
    Dec 14, 2014 at 20:54
  • 1
    $\begingroup$ Attempting unsolved problems like this (and failing..) can be a very fruitful learning exercise, if one comes in with the right mindset. $\endgroup$
    – Nick Alger
    Dec 15, 2014 at 19:23
  • $\begingroup$ however, some quibble: proofs/ claims have a validity to some small degree independent of "acceptance by the wider scientific community" and knowledge of them by particular individuals. eg when a correct proof is first introduced, it is not immediately/ instantaneously "accepted" by anyone other than the author. further support for this dynamic can be found in math history. & sometimes long periods can go between introduction of claims/ assertions and acceptance, eg in the case of Galois, Ramanujan etc $\endgroup$
    – vzn
    Dec 16, 2014 at 3:16
8
$\begingroup$

I would be very dubious that it has (in the sense of the proof of existence of a polynomial time algorithm). While it is not impossible that the paper is correct, there are a number of warning signs:

  1. The author has not published the result in a peer reviewed venue (even after 7 years).
  2. The author does not seem to have published anything else, anywhere.
  3. The paper presents the algorithms, but the claim of correctness is an informal handwaving argument about the complexity.
  4. For a problem that has resisted the attempts of some very clever people, the maths in the paper is too simple.
  5. The author doesn't appear to be affiliated with an academic institution. The new version of the paper clarifies this.

Again, without someone identifying a flaw in the paper, these are not fool proof signs. Maybe the author had a unique flash of insight and then moved on to a completely different life, but the weight of probability is against it - extraordinary claims require extraordinary evidence.

To elaborate on (4) given recent news, László Babai recently claimed a major improvement on known graph isomorphism algorithm (no preprint yet, but a decent running commentary on his public lecture can be found here), giving a pseudo-polynomial time algorithm. Babai and his colleagues are definitely very smart people, and the mathematics used to obtain this result is difficult, deep and spans graph theory and group theory. Given the weight of probability, this is the expected level for a significant advance on a problem like this.

Improve this answer
$\endgroup$
4
4
$\begingroup$

Laszlo Babai has claimed to have found a quasipolynomial solution for the graph isomorphism problem as of November 11th 2015.

... and retracted the claim yesterday (4/1/2017):

Source: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/

Improve this answer
$\endgroup$
4
  • $\begingroup$ From the link you provided: Babai has not yet released a preprint, and when I asked him he said “soon, soon.” Until then. $\endgroup$
    – Nobody
    Nov 14, 2015 at 2:43
  • $\begingroup$ The question doesn't define what it would mean for the graph isomorphism problem to count as solved, but the most likely interpretation is: that someone has found a polynomial-time algorithm for it, or given evidence that no such polynomial-time algorithm exists. Under that interpretation, this answer does not answer the question. $\endgroup$
    – D.W. ♦
    Nov 14, 2015 at 5:55
  • 4
    $\begingroup$ Babai retracted the claim of quasipolynomial runtime. Apparently there was an error in the analysis. $\endgroup$
    – Raphael ♦
    Jan 4, 2017 at 21:41
  • 1
    $\begingroup$ quasipolynomial claim restored $\endgroup$
    – miracle173
    Aug 9, 2017 at 5:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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