Thursday, November 19, 2015

A Quasipolynomial Time Algorithm for Graph Isomorphism

You can read the details at Math ∩ Programming, but here is the short version...

The claim is that 'there is a deterministic algorithm for graph isomorphism and it runs in 2O(logc(n)) for some constant c. Quantities which are exponential in some power of a logarithm are called 'quasipolynomial', hence the title.

In the background section of Jeremy's article (linked above), there is an image to illustrate different ways to draw the same graph:

Some of the commenters noted that Gis not the same as others. Can you prove or disprove that this is the case?
Here is an editable graph to help you. Single click fixes a node, double click releases it. You can drag the nodes.


(Adapted from mbostock's block #3750558)


1 comment: