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
Nov 02 2017
Cham, Springer
Other identifiers:

 Record created 2018-05-16, last modified 2020-10-28

Rate this document:

Rate this document:
(Not yet reviewed)