Polynomial Time Algorithm for Graph Isomorphism Testing | Hacker News Reader

Polynomial Time Algorithm for Graph Isomorphism Testing

arxiv.org

19 pointsamichail20 comments

This would be big news if true (though not P=NP-big; graph isomorphism is an apparently-hard problem that isn't known to be NP-hard).

From a cursory glance, it doesn't look terribly promising, but I haven't made a serious attempt to see what he's doing and how it might work. Examples of not-terribly-promising things:

1. He proves what he calls "Assertion 1", then says that it "suggests" some other propositions that he calls "Conclusion 1", "Conclusion 2", "Conclusion 3". He doesn't offer any proofs of these; they don't seem to be obvious consequences of Assertion 1; they don't even seem very likely to be true. In particular, Assertion 1 has the form "if graphs G and G' are isomorphic, then [linear algebra stuff]" and Conclusion 2 (which he uses later) has the form "if [linear algebra stuff] then graphs G and G' are isomorphic".

2. He then defines this thing he calls a W-matrix, which seems like it basically encodes for a given vertex of a given graph which other vertices are at any given distance from it. He then appears to claim -- I'm not quite sure, because his notation is eccentric and it's late at night -- that equality of W-matrices is basically the same thing as similarity of vertices (i.e., whether some graph automorphism carries one to the other), and that doesn't look right to me.

I repeat that I haven't looked at this carefully, and I'm not an expert in the field anyway. But it's not compelling enough to make me want to spend much more time on it; I expect that if it turns out to be valid someone smarter than me will check it over and let the world know :-).

Anyone can post to the ArXiv. So now wait a few weeks. One test: does his algorithm work for bipartite graphs? Another test: his algorithm uses real numbers. This is sketchy, as real numbers can't actually be represented in a computer.

The paper is pretty poorly written for two reasons: English is clearly not this guy's first language (no crime there, as it is said that the language of science is "heavily accented english") but he is also using a little too much handwaving for my comfort. This is a pretty math-heavy result, and this is not an airtight proof in any sense.

Basically: I agree with everything you said about it not being compelling enough for me to spend more time with it.

Fun fact so that I'll say more than "I agree": if GI is in P, the the polynomial hierarchy collapses to a level that I forget, and if GI is NPC it collapses to a PI_2! Neat!

> does his algorithm work for bipartite graphs?

Please, download the program and test any graph you like ;)

As an aside, theres some really beautiful results in graph theory that are only nicely expressible if you use linear algebra (aka spectral graph theory).

That being said, there are several problems with the paper: 1) it seems to implicitly assuming (without realizing it) that any two graphs it is considering at k-regular for some unspecified k. This is barely more general than assuming that graphs are planar, so itd be easy to have pretty reasonable algorithm for such a case (i'm pretty sure there are bunches in the research literature).

Also, it doesn't really seem to be addressing integrality of the linear programs, which i think is kinda key when using linear programs for combinatorics!

> they don't seem to be obvious consequences of Assertion 1

They do seem! In a few words, this fragment was cited from peer reviewed article http://dx.doi.org/10.1007/s11172-006-0105-6 .

> how it might work

Please, download the program and see...

The author appears to have done a fair bit of self-promotion in Wikipedia, which seems like a bad sign (though of course it doesn't prove anything): http://en.wikipedia.org/wiki/User_talk:Tim32 and http://en.wikipedia.org/w/index.php?title=Graph_isomorphism&... (see, e.g., a reversion from David Eppstein, who most certainly knows his stuff, saying "Persistent long-term self-promotion; blocking may be indicated.").

I can't help comparing this to the extreme absence of self-promotion in the most prominent example of somebody doing this who turned out to be the real thing (Perelman).

Yeah. But you've got to be careful; lots of people dismissed Louis de Branges' claim to have proved the Bieberbach conjecture because he also had a long history of self-promotion (and, indeed, of claiming to have proved things when his proofs really had holes). But he really did prove the Bieberbach conjecture.

Then again, he also keeps claiming to have proved the Riemann hypothesis and no one believes him :-).

You obviously know more about this than I do. That's a very interesting case.

One thing particularly interesting about this is that Graph Isomorphism is in a hypothetical category of problems sometimes dubbed "NP-intermediate": they are believed to be hard, but nobody has proven they're NP-complete. Linear programming used to be one of these, but was proven (rather brilliantly) to be in P by Leonid Khachiyan in 1979.

Notably, as far as I know, it hasn't been proven that NP-intermediate even exists. It's quite possible that all problems believed to be in that category are actually either P or NP-complete. If this proof is on the right track, this possibility may be all the more likely.

Context: http://en.wikipedia.org/wiki/Graph_isomorphism#Algorithmic_a...

tl;dr: Graph isomorphism recognition is an old and well-known problem that is in NP. It was not known whether it was NP-complete or in P, but this paper suggests that it is in P. This is kind of Big, assuming the paper's correct.

Hi, I’m Michael Trofimov, the author of this preprint.Thank you for your interest, you are welcome to ask your questions. More info about me you can find, for example, in Intel site: http://software.intel.com/sites/blackbelt/hall_of_fame.php (see Top Community Masterminds section). Is it self-promotion? ;-)

Yes, I am not native English speaker, so I would be very thankful if somebody will mark unclear statements in the paper and will suggest his/her version. Very important: this is preprint only! It is not final result, the investigation is under the progress. During discussion in other web-sites and via emails: one minor bug in the proof and one bug in program had been found. The program bug was fixed, also some time later I will upload the second version of the paper to arXiv.

All the best, -- Michael.

This makes me nervous: Further, without loss of generality of the task, we will consider undirected connected graphs without loops.

Tree isomorphism is polynomial. It's not obvious to me how you cut the loops out of two graphs and ensure you end up with similar trees. Quick scan didn't show that in the paper. I guess i'll have to read in more detail after dinner.

Loops as in "edges from vertex a to vertex a", not cycles, were discounted.

That's fine because you can ignore them until the end, and then just check your vertices for any loops, in O(n) time.

ah! that makes a whole lot more sense. thanks.

I'm not buying this until it's peer reviewed by someone like Brendan McKay.

Check out the acknowledgments.

What about them?

At least two of the people acknowledged are world famous algorithms researchers.

But it's not clear how much of the paper they looked at and whether they think it's correct.

Yeah, I'd be curious what the opinions of other researchers in this area are. There have been a number of debunked polynomial time algorithms for GI, so it's one of those things people are always skeptical of; but that of course doesn't mean this one is wrong too.

The author of the paper recently posted a blog comment in which he says he submitted to a few journals, and complains that "referees did not find any fatal error in my proof, but all the journals rejected this paper": http://rjlipton.wordpress.com/2009/05/04/an-approach-to-grap...

I'd take that as evidence that the referees at least didn't think it was a successful proof. The comment is attached to an old blog post about the problem from a well-known theoretical computer scientist (R.J. Lipton), but since it was posted about a year after the initial post, it hasn't gotten any replies.

Reply on news.ycombinator.com