Sherali-Adams relaxations of graph isomorphism polytopes

DOI10.1016/J.DISOPT.2014.01.004MaRDI QIDQ2339812zbMATH OpenOpenAlexFDO

Authors Peter N. Malkin

Publication date 9 April 2015

Published in Discrete Optimization (Search for Journal in Brave)

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)

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.

Recommendations

• Sherali-Adams relaxations and indistinguishability in counting logics
• Sherali-Adams relaxations and indistinguishability in counting logics
• PEBBLE GAMES AND LINEAR EQUATIONS
• Sherali-Adams relaxations of the matching polytope
• Lov\'asz Meets Weisfeiler and Leman

Cites work

• scientific article; zbMATH DE number 5485464 (Why is no real title available?)
• scientific article; zbMATH DE number 3823850 (Why is no real title available?)
• A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• An Efficient Algorithm for Graph Isomorphism
• An optimal lower bound on the number of variables for graph identification
• Complexity analyses of Bienstock-Zuckerberg and lasserre relaxations on the matching and stable set polytopes
• Cones of Matrices and Set-Functions and 0–1 Optimization
• Global optimization with polynomials and the problem of moments
• Graph isomorphism and theorems of Birkhoff type
• Integrality gaps for Sherali-Adams relaxations
• On a representation of the matching polytope via semidefinite liftings
• 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
• Random Graph Isomorphism
• Recognizing graph theoretic properties with polynomial ideals
• Sherali-Adams relaxations of the matching polytope
• The graph isomorphism disease

Cited in

(18)

• Sherali-Adams relaxations and indistinguishability in counting logics
• On the expressive power of linear algebra on graphs
• Limitations of algebraic approaches to graph isomorphism testing
• On Tinhofer's linear programming approach to isomorphism testing
• The QAP-polytope and the graph isomorphism problem
• Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas
• Lasserre hierarchy for graph isomorphism and homomorphism indistinguishability
• Graph isomorphism, color refinement, and compactness
• Sherali-Adams relaxations and indistinguishability in counting logics
• On the expressive power of linear algebra on graphs
• A finite-model-theoretic view on propositional proof complexity
• A completely positive formulation of the graph isomorphism problem and its positive semidefinite relaxation
• scientific article; zbMATH DE number 7561610 (Why is no real title available?)
• PEBBLE GAMES AND LINEAR EQUATIONS
• Lov\'asz Meets Weisfeiler and Leman
• Cutting planes width and the complexity of graph isomorphism refutations
• scientific article; zbMATH DE number 7559112 (Why is no real title available?)
• Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem

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)