On the linear extension complexity of stable set polytopes for perfect graphs

DOI10.1016/J.EJC.2018.02.014MaRDI QIDQ2311370zbMATH OpenOpenAlexFDO

Authors Hao Hu, Monique Laurent

Publication date 10 July 2019

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1706.05496, https://ir.cwi.nl/pub/27494

zbMATH Keywords

basic perfect graphsstable set polytopes of perfect graphs

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76) Perfect graphs (05C17)

Abstract: We study the linear extension complexity of stable set polytopes of perfect graphs. We make use of known structural results permitting to decompose perfect graphs into basic perfect graphs by means of two graph operations: 2-join and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behaviour of the extension complexity under these graph operations. We show bounds for the extension complexity of the stable set polytope of a perfect graph $G$ depending linearly on the size of $G$ and involving the depth of a decomposition tree of $G$ in terms of basic perfect graphs.

Recommendations

• Extension complexity of stable set polytopes of bipartite graphs
• Extension complexity of independent set polytopes
• Extension complexity of the correlation polytope

Cites work

• scientific article; zbMATH DE number 3878985 (Why is no real title available?)
• A characterization of perfect graphs
• Berge trigraphs
• Coloring perfect graphs with no balanced skew-partitions
• Colouring perfect graphs with bounded clique number
• Combinatorial bounds on nonnegative rank and extended formulations
• Combinatorial optimization with 2-joins
• Compositions for perfect graphs
• Exponential lower bounds for polytopes in combinatorial optimization
• Extended formulations in combinatorial optimization
• Extension complexity of stable set polytopes of bipartite graphs
• Fast Skew Partition Recognition
• Lifts of Convex Sets and Cone Factorizations
• Lower bounds on the size of semidefinite programming relaxations
• Normal hypergraphs and the perfect graph conjecture
• On certain polytopes associated with graphs
• On the perfect graph conjecture
• Smallest compact formulation for the permutahedron
• Some \(0/1\) polytopes need exponential size extended formulations
• Stable sets and graphs with no even holes
• Star-cutsets and perfect graphs
• The ellipsoid method and its consequences in combinatorial optimization
• The strong perfect graph theorem
• Using separation algorithms to generate mixed integer model reformulations

Cited in

(5)

• Maximum semidefinite and linear extension complexity of families of polytopes
• Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs
• On extracting maximum stable sets in perfect graphs using Lovász's theta function
• The stable set polytope of quasi-line graphs
• Extension complexity of stable set polytopes of bipartite graphs

This page was built for publication: On the linear extension complexity of stable set polytopes for perfect graphs

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