Extension complexity of stable set polytopes of bipartite graphs

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 Ω(nlogn) 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)|.


Published in:
Lecture Notes in Computer Science book series (LNCS), 10520, 75-87
Presented at:
WG 2017: Graph-Theoretic Concepts in Computer Science, Eindhoven, The Netherlands, June 21-23 2017
Year:
Nov 02 2017
Publisher:
Cham, Springer
ISBN:
978-3-319-68704-9
Keywords:
Other identifiers:
Laboratories:




 Record created 2018-05-16, last modified 2019-06-19


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)