Sherali-Adams relaxations of graph isomorphism polytopes

DOI10.1016/J.DISOPT.2014.01.004zbMATH Open1308.90210arXiv1107.0632OpenAlexW2963840360MaRDI QIDQ2339812FDOQ2339812

Peter N. Malkin

Publication date: 9 April 2015

Published in: Discrete Optimization (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1107.0632

zbMATH Keywords

graph isomorphismWeisfeiler-Lehman algorithmSherali-Adams relaxations

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph isomorphism and theorems of Birkhoff type
• Global optimization with polynomials and the problem of moments
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Cones of Matrices and Set-Functions and 0–1 Optimization
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• Random Graph Isomorphism
• The graph isomorphism disease
• An optimal lower bound on the number of variables for graph identification
• Integrality gaps for Sherali-Adams relaxations
• Sherali-adams relaxations of the matching polytope
• Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes
• An Efficient Algorithm for Graph Isomorphism
• On construction and identification of graphs. With contributions by A. Lehman, G. M. Adelson-Velsky, V. Arlazarov, I. Faragev, A. Uskov, I. Zuev, M. Rosenfeld and B. Weisfeiler
• On a representation of the matching polytope via semidefinite liftings
• Recognizing graph theoretic properties with polynomial ideals

Cited In (16)

• Lov\'asz Meets Weisfeiler and Leman
• On the expressive power of linear algebra on graphs
• Title not available (Why is that?)
• The QAP-polytope and the graph isomorphism problem
• A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation
• Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability
• Limitations of Algebraic Approaches to Graph Isomorphism Testing
• Title not available (Why is that?)
• On Tinhofer’s Linear Programming Approach to Isomorphism Testing
• Title not available (Why is that?)
• Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem
• Graph isomorphism, color refinement, and compactness
• Cutting planes width and the complexity of graph isomorphism refutations
• PEBBLE GAMES AND LINEAR EQUATIONS
• Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas
• Title not available (Why is that?)

This page was built for publication: Sherali-Adams relaxations of graph isomorphism polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2339812)