HiveBrain v1.2.0
Get Started
← Back to all entries
patternMajor

Has the graph isomorphism problem been solved?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
problemthegraphbeenhassolvedisomorphism

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#35260, answer score: 24

Revisions (0)

No revisions yet.