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 language | English |
---|---|
Pages (from-to) | 1931-1944 |
Number of pages | 14 |
Journal | Graphs and combinatorics |
Volume | 32 |
Issue number | 5 |
DOIs | |
Publication status | Published - 1 Sept 2016 |
Externally published | Yes |
Keywords
- Decomposition
- Extended formulation
- Independence polytope
- Regular matroid