Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Extension complexity of stable set polytopes of bipartite graphs
 
conference paper

Extension complexity of stable set polytopes of bipartite graphs

Aprile, Manuel Francesco  
•
Faenza, Yuri  
•
Fiorini, Samuel
Show more
November 2, 2017
Lecture Notes in Computer Science book series (LNCS)
WG 2017: Graph-Theoretic Concepts in Computer Science

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

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-319-68705-6_6
ArXiv ID

1702.08741

Author(s)
Aprile, Manuel Francesco  
Faenza, Yuri  
Fiorini, Samuel
Huynh, Tony
Macchia, Marco
Date Issued

2017-11-02

Publisher

Springer

Publisher place

Cham

Published in
Lecture Notes in Computer Science book series (LNCS)
ISBN of the book

978-3-319-68704-9

Volume

10520

Start page

75

End page

87

Subjects

Extension complexity

•

Stable set polytope

•

Bipartite graphs

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Event nameEvent placeEvent date
WG 2017: Graph-Theoretic Concepts in Computer Science

Eindhoven, The Netherlands

June 21-23 2017

Available on Infoscience
May 16, 2018
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/146450
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés