Extended Formulations for Sparsity Matroids

Abstract

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 formulation is $O(|V||E|)$ when $k\ge \ell$ and $O(|V{|}^2|E|)$ when $k\le \ell$. To this end, we employ the technique developed by Faenza et al. recently that uses a randomized communication protocol.

10 pages