Sparse parameterized problems

DOI10.1016/0168-0072(95)00069-0MaRDI QIDQ2564046zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Marco Cesati, Michael R. Fellows

Publication date 13 February 1997

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(95)00069-0

complexity theory for parametrized problems Mahaney's theorem for sparse sets

Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Review text

Mike Fellows and the reviewer developed a complexity theory for parametrized problems: that is, problems of the form: \[ \begin{aligned} \text{Input} \quad & \langle x,k \rangle\\ \text{Parameter} \quad & k \\ \text{Question} \quad & \text{Is } \langle x,k \rangle \in L? \end{aligned} \] For instance, VERTEX COVER is (classically) NP complete, but as a parametrized problem, it is fixed parameter tractable, meaning that there is an algorithm \(A\) and a constant \(c\) \((=1)\) for VERTEX COVER) such that \(A\) decides, for a fixed \(k\), if \(G\) has a vertex cover of size \(k\) in terms \(O (|G |^c)\). On the other hand, there are problems where only brute force seems possible. These give rise to parameter classes akin to NP. The paper at hand examines the analogue of Mahaney's Theorem for sparse sets to the parametric setting. The analogue is found to hold, but the combinatorics are significantly more difficult.

Recommendations

Cites work

Cited in

(6)

This page was built for publication: Sparse parameterized problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2564046)