Extension complexity of stable set polytopes of bipartite graphs

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 $\mathsf{STAB}(G)$ be the convex hull of the stable sets of $G$. It is easy to see that $n⩽\mathsf{xc}(\mathsf{STAB}(G))⩽n+m$. We improve both of these bounds. For the upper bound, we show that $\mathsf{xc}(\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}(\mathsf{STAB}(G))$ is $\Omega (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)|$.

13 pages, 2 figures

References in corpus (2)

• Extended Formulations in Combinatorial Optimization
• Fooling Sets and the Spanning Tree Polytope

Cited by in corpus (3)

• On 2-level polytopes arising in combinatorial settings
• Extended formulations from communication protocols in output-efficient time
• On the Linear Extension Complexity of Stable Set Polytopes for Perfect Graphs