Albert Atserias (Universitat Politecnica de Catalunya, Barcelona)
Wednesday, 5.2.2014, 12:30
Abstract: The graph isomorphism problem is one of the most celebrated computational problems whose complexity status lies somewhere intermediate between P and NP-complete. We revisit two very different-looking relaxations of the problem. In the first relaxation we require the graphs to preserve the number of types of local neighborhoods through the well-known vertex-refinement heuristic and its obvious extension to refinement of $k$-tuples. In the second relaxation we write the natural 0-1 linear program for graph isomorphism and relax it to the continuum through the hierarchy of continuous relaxations suggested by Sherali and Adams for general 0-1 combinatorial problems.
We show that these two very different-looking relaxations are indeed equivalent. An interesting consequence of this is that the graph isomorphism problem restricted to planar graphs can be solved by an explicit polynomial-size linear program.