3 ms·
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
by bitL 10y ago
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.
- CJefferson 10y agoNope, 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.
- bonzini 10y agoIsn't VF2 faster than Nauty?
- CJefferson 10y agoVF2 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).
- adrianN 10y agoAsymptotically 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.
- CJefferson 10y agoGraph 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.
- maverick_iceman 10y agoReminds me of the Simplex algorithm.
- thomasahle 10y agoI 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.