Sparse parameterized problems (Q2564046)

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.