The Taub Faculty of Computer Science Events and Talks

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.