The Complexity of Deletion Problems for Matroids
Michael Snook · SIAM Journal on Discrete Mathematics · 2013
A matroid property is a class of matroids that is closed under isomorphism. The matroid $\pi$ deletion problem is as follows: Given a matroid $M$ and integer $k$, can we delete at most $k$ elements from $M$ such that the resulting matroid satisfies the property $\pi$? If we assume that $\pi$ is hereditary, nontrivial, and completely closed under series and parallel extensions, then the $\pi$ deletion problem is NP-hard when the input consists of (i) a $GF(q)$ representation or (ii) the list of independent sets. We also show that for many natural properties, the $\pi$ deletion problem cannot be solved in polynomial time by a Turing machine that is equipped with an independence oracle.