Constant-Time Algorithms for Sparsity Matroids

Hiro Ito, Shin-ichi Tanigawa, Yuichi Yoshida

A graph $G=(V,E)$ is called $(k,\ell )$-full if $G$ contains a subgraph $H=(V,F)$ of $k|V|-\ell$ edges such that, for any non-empty $F^{\prime }\subseteq F$, $|F^{\prime }|\le k|V(F^{\prime })|-\ell$ hol…