Sherali--Adams Relaxations and Indistinguishability in Counting Logics
Authors:
- Albert AtseriasAAAlbert Atserias
- Elitza ManevaEMElitza Maneva
Open Access
- 1 January 2013
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 42 (1) , 112-137
Abstract
Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the linear programming relaxation known as fractional isomorphism. We show that the levels of the Sherali--Adams (SA) hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well-known color-refinement heuristic for graph isomorphism called the Weisfeiler--Lehman algorithm, or, equivalently, with the levels of indistinguishability in a logic with counting quantifiers and a bounded number of variables. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers that a fixed number of levels of SA suffice to determine isomorphism of planar and minor-free graphs. We also offer applications in both finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs, such as that of having a flow circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer, and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to $\Omega(n)$ levels, where $n$ is the number of vertices in the graph.
Keywords
This publication has 31 references indexed in Scilit:
- Affine systems of equations and counting infinitary logicTheoretical Computer Science, 2009
- Vertex cover might be hard to approximate to withinJournal of Computer and System Sciences, 2008
- Global Optimization with Polynomials and the Problem of MomentsSIAM Journal on Optimization, 2001
- Conjunctive-Query Containment and Constraint SatisfactionJournal of Computer and System Sciences, 2000
- Generalized quantifiers and pebble games on finite structuresAnnals of Pure and Applied Logic, 1995
- Fractional isomorphism of graphsDiscrete Mathematics, 1994
- An optimal lower bound on the number of variables for graph identificationCombinatorica, 1992
- Cones of Matrices and Set-Functions and 0–1 OptimizationSIAM Journal on Optimization, 1991
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming ProblemsSIAM Journal on Discrete Mathematics, 1990
- Random Graph IsomorphismSIAM Journal on Computing, 1980