Extension Complexity of Stable Set Polytopes of Bipartite Graphs

Manuel Aprile, Yuri Faenza, Samuel Fiorini, Tony Huynh, Marco Macchia

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

10 Citations (Scopus)


The extension complexity 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 STAB(G) be the convex hull of the stable sets of G. It is easy to see that n⩽ xc(STAB(G)) ⩽ n+ m. We improve both of these bounds. For the upper bound, we show that xc(STAB(G)) is O(n2logn), which is an improvement when G has quadratically many edges. For the lower bound, we prove that xc(STAB(G)) is Ω(nlog 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)|.

Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication43rd International Workshop, WG 2017 Eindhoven, The Netherlands, June 21–23, 2017 Revised Selected Papers
EditorsHans L. Bodlaender, Gerhard J. Woeginger
Place of PublicationCham Switzerland
Number of pages13
ISBN (Electronic)9783319687056
ISBN (Print)9783319687049
Publication statusPublished - 1 Jan 2017
Externally publishedYes
Event43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017 - Eindhoven, Netherlands
Duration: 21 Jun 201723 Jun 2017

Publication series

NameLecture Notes in Computer Science
Volume10520 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017

Cite this