Extension complexity of the correlation polytope

DOI10.1016/J.ORL.2018.12.001MaRDI QIDQ2294265zbMATH OpenOpenAlexWikidataFDO

Authors Pierre Aboulker, Samuel Fiorini, Tony Huynh, Marco Macchia, Johanna Seif

Publication date 10 February 2020

Published in Operations Research Letters (Search for Journal in Brave)

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

zbMATH Keywords

machine learningtreewidthgraph minorsextension complexitycorrelation polytope

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Structural characterization of families of graphs (05C75)

Abstract: We prove that for every $n$-vertex graph $G$, the extension complexity of the correlation polytope of $G$ is $2^{O(mathrmtw(G)+logn)}$, where $mathrmtw(G)$ is the treewidth of $G$. Our main result is that this bound is tight for graphs contained in minor-closed classes.

Recommendations

• A short proof that the extension complexity of the correlation polytope grows exponentially
• Extension complexity of independent set polytopes
• Extension complexity, MSO logic, and treewidth

Cites work

• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A short proof that the extension complexity of the correlation polytope grows exponentially
• Communication complexity (for algorithm designers)
• Correlation polytopes: Their geometry and complexity
• Exponential lower bounds for polytopes in combinatorial optimization
• Extended formulation for CSP that is compact for instances of bounded treewidth
• Extended formulations in combinatorial optimization
• Extension complexity of independent set polytopes
• Graph minors. XX: Wagner's conjecture
• Graphical models, exponential families, and variational inference
• Integer Programming
• Linear min-max relation between the treewidth of \(H\)-minor-free graphs and its largest grid
• Linearity of grid minors in treewidth with applications through bidimensionality
• Planar Formulae and Their Uses
• Polynomial bounds for the grid-minor theorem
• Some \(0/1\) polytopes need exponential size extended formulations

Cited in

(10)

• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Extension complexity, MSO logic, and treewidth
• The Complexity of Problems in P Given Correlated Instances
• Parameterized extension complexity of independent set and related problems
• A short proof that the extension complexity of the correlation polytope grows exponentially
• New limits of treewidth-based tractability in optimization
• Extension complexity of independent set polytopes
• On the linear extension complexity of stable set polytopes for perfect graphs
• Extension complexity, MSO logic, and treewidth
• Correlation polytopes: Their geometry and complexity

This page was built for publication: Extension complexity of the correlation polytope

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