TY - GEN

T1 - Extension Complexity of Stable Set Polytopes of Bipartite Graphs

AU - Aprile, Manuel

AU - Faenza, Yuri

AU - Fiorini, Samuel

AU - Huynh, Tony

AU - Macchia, Marco

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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)|.

AB - 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)|.

UR - http://www.scopus.com/inward/record.url?scp=85034041875&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-68705-6_6

DO - 10.1007/978-3-319-68705-6_6

M3 - Conference Paper

AN - SCOPUS:85034041875

SN - 9783319687049

T3 - Lecture Notes in Computer Science

SP - 75

EP - 87

BT - Graph-Theoretic Concepts in Computer Science

A2 - Bodlaender, Hans L.

A2 - Woeginger, Gerhard J.

PB - Springer

CY - Cham Switzerland

T2 - 43rd International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2017

Y2 - 21 June 2017 through 23 June 2017

ER -