Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: On Continuous and Combinatorial Relaxations of Graph Isomorphism
event speaker icon
Albert Atserias (Universitat Politecnica de Catalunya, Barcelona)
event date icon
Wednesday, 05.02.2014, 12:30
event location icon
Taub 201
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.