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 -