15.1. Kernelization and Fixed-Parameter Tractability

Theorem 15.1: A parameterized decision problem \(\Pi\) is fixed-parameter tractable if and only if it has a problem kernel.

Proof: The "if" direction is obvious because, as explained in the introduction of this chapter, a polynomial-time kernelization algorithm can be used to obtain an algorithm that decides any problem instance \((I,k)\) in \(O(g(k) + |I|^c)\) time, for some function \(g\) and constant \(c\).

For the "only if" direction, assume we are given a parameterized algorithm \(\mathcal{A}\) for problem \(\Pi\) with running time \(f(k) \cdot |I|^c\). To obtain a polynomial-time kernelization algorithm for \(\Pi\), we run \(\mathcal{A}\) on a given instance \((I,k)\) for up to \(|I|^{c+1}\) steps. If the algorithm terminates in this time bound, we return a trivial yes or no-instance of constant size depending on whether the algorithm answers "Yes" or "No". This constant-size instance clearly has size \(O(f(k))\). If the algorithm does not terminate in \(|I|^{c+1}\) steps, then we return \((I,k)\) as the problem kernel. Since \(\mathcal{A}\) has running time \(f(k) \cdot |I|^c\) and does not terminate after \(|I|^{c+1}\) steps on the instance \((I,k)\), we have \(|I| \le f(k)\). Thus, \(I\) is a problem kernel of size bounded by \(f(k)\). ▨