Sherali-Adams Relaxations of Graph Isomorphism Polytopes

Details Sherali-Adams Relaxations of Graph Isomorphism Polytopes Sherali-Adams Relaxations of Graph Isomorphism Polytopes

2011-07-04

arxiv.org/abs/1107.0632v2

Mathematics

Combinatorics

Scientific paper

We investigate the Sherali-Adams lift & project hierarchy applied to a graph isomorphism polytope whose integer points encode the isomorphisms between two graphs. In particular, the Sherali-Adams relaxations characterize a new vertex classification algorithm for graph isomorphism, which we call the generalized vertex classification algorithm. This algorithm generalizes the classic vertex classification algorithm and generalizes the work of Tinhofer on polyhedral methods for graph automorphism testing. We establish that the Sherali-Adams lift & project hierarchy when applied to a graph isomorphism polytope needs Omega(n) iterations in the worst case before converging to the convex hull of integer points. We also show that this generalized vertex classification algorithm is also strongly related to the well-known Weisfeiler-Lehman algorithm, which we show can also be characterized in terms of the Sherali-Adams relaxations of a semi-algebraic set whose integer points encode graph isomorphisms.

Affiliated with

Also associated with

No associations

Rating

Sherali-Adams Relaxations of Graph Isomorphism Polytopes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sherali-Adams Relaxations of Graph Isomorphism Polytopes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sherali-Adams Relaxations of Graph Isomorphism Polytopes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-4261