News for hackers. Stuff that matters.
Re:Graph Isomorphism Strikes Back by bitL on Friday January 06, 2017 @05:05AM (#13335172)
It's already the fastest algorithm available. Not sure why anyone would need to salvage his ideas; anyone needing state-of-art graph isomorphism algorithm will implement it.
Re:Graph Isomorphism Strikes Back by CJefferson on Friday January 06, 2017 @05:10AM (#13335195)
Nope, it's theoretically amazing interesting, but anyone who really wants to solve graph isomorphism would use Brendan McKay's Nauty, or one of the up-to-date implementations (Saucy, Bliss, Hungry, Ferret).

Personal interest: I wrote Ferret, my PhD student wrote Hungry.

Re:Graph Isomorphism Strikes Back by bonzini on Friday January 06, 2017 @07:02AM (#13335660)
Isn't VF2 faster than Nauty?
Re:Graph Isomorphism Strikes Back by CJefferson on Friday January 06, 2017 @07:23AM (#13335757)
VF2 is faster than Nauty for EXTREMELY trivial problems (and many problems are extremely triial), but I've found many real-world problems where it falls off a cliff.

VF2 is basically the most stupid search imaginable -- if the problem is easy it stumbles into the solution very quickly, but if any work is required it degrades into a horrible exponential search.

On the other hand, Nauty is very difficult to confuse -- as it reasons about the whole graph (whereas VF2 just does local reasoning), your graph has to have global properties which make it hard, which are rare (and basically never occur in real-world graphs, unless they come from some mathematical problem).

Re:Graph Isomorphism Strikes Back by thomasahle on Friday January 06, 2017 @07:32AM (#13335801)
I recall him saying in a talk, that there is no need to implement his algorithm. In a way the algorithm proves that there are no very hard isomorphism cases, which then guarantees that our other practical heuristic algorithms can't do as badly as we might have feared.
Re:Graph Isomorphism Strikes Back by adrianN on Friday January 06, 2017 @05:22AM (#13335262)
Asymptotically fastest is unfortunately very different from fastest in practice. I mean salvage his ideas towards a quasipolynomial (or even polynomial!) algorithm for graph isomorphism. I don't really expect a practical algorithm for the problem in the near future.
Re:Graph Isomorphism Strikes Back by CJefferson on Friday January 06, 2017 @05:45AM (#13335373)
Graph isomorphism is interesting, in that practical algorithms already exist. It's actually very, very hard to produce difficult instances of the graph isomorphism problem (to be exact, instances where existing algorithms take non-polynomial time).

Much of the progress in recent years has come from first finding instances where existing algorithms (in particular, partitioning from Brendan McKay's Nauty) take exponential time, and understanding why.

Re:Graph Isomorphism Strikes Back by maverick_iceman on Friday January 06, 2017 @07:57AM (#13335899)
Reminds me of the Simplex algorithm.