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-joins and skew partitions. Exploiting the link between extension complexity and the nonnegative rank of an associated slack matrix, we investigate the behavior 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.
Additional Metadata
Persistent URL dx.doi.org/10.1016/j.ejc.2018.02.014
Journal European Journal of Combinatorics
Note Please cite this article in press as: H. Hu, M. Laurent, On the linear extension complexity of stable set polytopes for perfect graphs, European Journal of Combinatorics (2018), https://doi.org/10.1016/j.ejc.2018.02.014
Citation
Hu, H, & Laurent, M. (2018). On the linear extension complexity of stable set polytopes for perfect graphs. European Journal of Combinatorics. doi:10.1016/j.ejc.2018.02.014