The Complexity of Deletion Problems for Matroids
Autor: | Michael Snook |
---|---|
Rok vydání: | 2013 |
Předmět: | |
Zdroj: | SIAM Journal on Discrete Mathematics. 27:402-421 |
ISSN: | 1095-7146 0895-4801 |
Popis: | 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. |
Databáze: | OpenAIRE |
Externí odkaz: |