Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
Extension Complexity of Stable Set Polytopes of Bipartite Graphs
verfasst von : Manuel Aprile, Yuri Faenza, Samuel Fiorini, Tony Huynh, Marco Macchia
Erschienen in: Graph-Theoretic Concepts in Computer Science
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
The extension complexity \(\mathsf {xc}(P)\) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let \({{\mathrm{\mathsf {STAB}}}}(G)\) be the convex hull of the stable sets of G. It is easy to see that \(n \leqslant \mathsf {xc}({{\mathrm{\mathsf {STAB}}}}(G)) \leqslant n+m\). We improve both of these bounds. For the upper bound, we show that \(\mathsf {xc}({{\mathrm{\mathsf {STAB}}}}(G))\) is \(O(\frac{n^2}{\log n})\), which is an improvement when G has quadratically many edges. For the lower bound, we prove that \(\mathsf {xc}({{\mathrm{\mathsf {STAB}}}}(G))\) is \(\varOmega (n \log n)\) when G is the incidence graph of a finite projective plane. We also provide examples of 3-regular bipartite graphs G such that the edge vs stable set matrix of G has a fooling set of size |E(G)|.