Extension complexity of stable set polytopes of bipartite graphs

Manuel Aprile, Yuri Faenza, Samuel Fiorini +2

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$ verti…