The Complexity of Deletion Problems for Matroids

Autor:	Michael Snook
Rok vydání:	2013
Předmět:	Discrete mathematics Combinatorics Oriented matroid Graphic matroid Integer General Mathematics Weighted matroid Matroid partitioning Isomorphism Time complexity Matroid Mathematics
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:	https://explore.openaire.eu/search/publication?articleId=doi_________::49c9618ef967ed1a48d45f61a11d7e59 https://doi.org/10.1137/110852383 Zobrazit plný text záznamu