Subgraph polytopes and independence polytopes of count matroids

Michele Conforti, Volker Kaibel, Matthias Walter*, Stefan Weltge

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

12 Citations (Scopus)
38 Downloads (Pure)

Abstract

Given a graph, the non-empty subgraph polytope is the convex hull of the characteristic vectors of all pairs (F,S) where S is a non-empty subset of nodes and F is a subset of the edges with both endnodes in S. We obtain a strong relationship between non-empty subgraph polytopes and spanning forest polytopes relating their extension complexities. We further show that these polytopes provide polynomial size extended formulations for independence polytopes of count matroids, generalizing recent results on sparsity matroids.

Original languageEnglish
Article number5968
Pages (from-to)457-460
Number of pages4
JournalOperations research letters
Volume43
Issue number5
DOIs
Publication statusPublished - 14 Jul 2015
Externally publishedYes

Keywords

  • Count matroids
  • Extension complexity
  • Spanning tree polytope
  • n/a OA procedure

Fingerprint

Dive into the research topics of 'Subgraph polytopes and independence polytopes of count matroids'. Together they form a unique fingerprint.

Cite this