Extended Formulations for Independence Polytopes of Regular Matroids

Volker Kaibel, Jon Lee, Matthias Walter, Stefan Weltge*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

5 Citations (Scopus)

Abstract

We show that the independence polytope of every regular matroid has an extended formulation of size quadratic in the size of its ground set. This generalizes a similar statement for (co-)graphic matroids, which is a simple consequence of Martin’s extended formulation for the spanning-tree polytope. In our construction, we make use of Seymour’s decomposition theorem for regular matroids. As a consequence, the extended formulations can be computed in polynomial time.

Original languageEnglish
Pages (from-to)1931-1944
Number of pages14
JournalGraphs and combinatorics
Volume32
Issue number5
DOIs
Publication statusPublished - 1 Sept 2016
Externally publishedYes

Keywords

  • Decomposition
  • Extended formulation
  • Independence polytope
  • Regular matroid

Fingerprint

Dive into the research topics of 'Extended Formulations for Independence Polytopes of Regular Matroids'. Together they form a unique fingerprint.

Cite this