Average case polyhedral complexity of the maximum stable set problem

DOI10.1007/S10107-016-0989-3MaRDI QIDQ344955zbMATHOpenAlexFDO

Authors Gábor Braun, Samuel Fiorini, Sebastian Pokutta

Publication date 25 November 2016

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

linear programs

Mathematics Subject Classification ID

Linear programming (90C05) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We study the minimum number of constraints needed to formulate random instances of the maximum stable set problem via linear programs (LPs), in two distinct models. In the uniform model, the constraints of the LP are not allowed to depend on the input graph, which should be encoded solely in the objective function. There we prove a $2^{Omega(n/logn)}$ lower bound with probability at least $1-2^{-2^n}$ for every LP that is exact for a randomly selected set of instances; each graph on at most n vertices being selected independently with probability $$. In the non-uniform model, the constraints of the LP may depend on the input graph, but we allow weights on the vertices. The input graph is sampled according to the G(n, p) model. There we obtain upper and lower bounds holding with high probability for various ranges of p. We obtain a super-polynomial lower bound all the way from $p=Omega(lo{g}^{6+varepsilon}/n)$ to $p=o(1/logn)$. Our upper bound is close to this as there is only an essentially quadratic gap in the exponent, which currently also exists in the worst-case model. Finally, we state a conjecture that would close this gap, both in the average-case and worst-case models.

Recommendations

• Average case polyhedral complexity of the maximum stable set problem
• On the Power of Symmetric Linear Programs
• Are stable instances easy?
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Exponential lower bounds for polytopes in combinatorial optimization

Cites work

• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• A linear-size zero-one programming model for the minimum spanning tree problem in planar graphs
• A note on the extension complexity of the knapsack polytope
• A short proof that the extension complexity of the correlation polytope grows exponentially
• An information complexity approach to extended formulations
• Approximate Constraint Satisfaction Requires Large LP Relaxations
• Approximation Limits of Linear Programs (Beyond Hierarchies)
• Common information and unique disjointness
• Exponential lower bounds for polytopes in combinatorial optimization
• Expressing combinatorial optimization problems by linear programs
• Extended formulations in combinatorial optimization
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Inapproximability of combinatorial problems via small LPs and SDPs
• Linear vs. semidefinite extended formulations
• Lower bounds on the size of semidefinite programming relaxations
• Maximum matching and a polyhedron with 0,1-vertices
• Nondeterministic Quantum Query and Communication Complexities
• On the distributional complexity of disjointness
• Some \(0/1\) polytopes need exponential size extended formulations
• The matching polytope does not admit fully-polynomial size relaxation schemes

Cited in

(6)

• New limits of treewidth-based tractability in optimization
• Average case polyhedral complexity of the maximum stable set problem
• Persistency of linear programming relaxations for the stable set problem
• Exponential lower bounds for polytopes in combinatorial optimization
• Affine reductions for LPs and SDPs
• A note on “A linear‐size zero‐one programming model for the minimum spanning tree problem in planar graphs”

This page was built for publication: Average case polyhedral complexity of the maximum stable set problem

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