On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs
arXiv:1706.05496 · doi:10.1016/j.ejc.2018.02.014
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 depending linearly on the size of and involving the depth of a decomposition tree of in terms of basic perfect graphs.
arXiv comment17 pages
References in corpus (6)
- Lifts of convex sets and cone factorizations
- Introduction to Nonnegative Matrix Factorization
- Combinatorial optimization with 2-joins
- Coloring perfect graphs with no balanced skew-partitions
- Colouring perfect graphs with bounded clique number
- Extension complexity of stable set polytopes of bipartite graphs