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 language | English |
---|---|
Article number | 5968 |
Pages (from-to) | 457-460 |
Number of pages | 4 |
Journal | Operations research letters |
Volume | 43 |
Issue number | 5 |
DOIs | |
Publication status | Published - 14 Jul 2015 |
Externally published | Yes |
Keywords
- Count matroids
- Extension complexity
- Spanning tree polytope
- n/a OA procedure