Extended Formulations for Sparsity Matroids

Satoru Iwata, Naoyuki Kamiyama, Naoki Katoh +2

We show the existence of a polynomial-size extended formulation for the base polytope of a $(k,\ell )$-sparsity matroid. For an undirected graph $G=(V,E)$, the size of the formulati…