Average case polyhedral complexity of the maximum stable set problem

DOI10.1007/S10107-016-0989-3zbMATH Open1350.05152arXiv1311.4001OpenAlexW1832679686MaRDI QIDQ344955FDOQ344955

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)

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.

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

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

zbMATH Keywords

linear programs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (5)

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

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)