14.2. Fixed-Parameter Tractability

Fixed-parameter tractability requires a bit more care to define formally. The intuitive idea, which justifies the name "fixed-parameter tractable problem", is that we measure the difficulty of an input not only in terms of its input size but also in terms of some hardness parameter \(k\). Whenever \(k\) is a constant—is "fixed"—then we want to be able to guarantee that we can solve any instance of size \(n\) efficiently, that is, in polynomial time.

An algorithm with running time \(O\bigl(n^k\bigr)\) or \(O\Bigl(n^{k^k}\Bigr)\) would satisfy this requirement, but such algorithms are generally not very useful because the polynomial is small enough to translate into an efficient running time only if \(k\) is very small. Thus, the actual definition of fixed-parameter tractability is stricter. We want an algorithm whose running time depends polynomially on the input size, whose dependence on the parameter is some arbitrary computable function—usually, we aim for a function of the form \(f(k) = c^k\), but this is not always achievable—and the polynomial in \(n\) and the function \(f(k)\) are independent of each other.

To express this formally, we need the notion of a parameterized decision problem. Recall the notion of a decision problem, a problem that asks a yes/no question on any given input. We call an input a yes-instance if the answer for this input is yes, and a no-instance if the answer is no. Also recall the equivalence between decision problems and formal languages: We can encode the inputs to our problem using an appropriate encoding over some alphabet \(\Sigma\), for example, as bit strings to be stored in our computer's memory. Then our decision problem is equivalent to deciding the membership of any string \(\sigma \in \Sigma^*\) in the language \(\mathcal{L} \subseteq \Sigma^*\) of all strings that encode yes-instances of our problem. The following definition introduces the concept of a (hardness) parameter into the definition of a decision problem.

A parameterized decision problem is a language \(\mathcal{L} \subseteq \Sigma^* \times \mathbb{N}\). For an instance \((x,k) \in \Sigma^* \times \mathbb{N}\), \(k\) is called the parameter of the instance.

For example, if the problem we want to solve is the vertex cover problem, an instance \((G,k)\) of the parameterized version of the problem consists of (an appropriate encoding of) a graph \(G\) and some integer \(k\). This integer \(k\) can represent anything but is often related to the solution we are looking for.¹ For the vertex cover problem, a natural choice of \(k\) is the size of the vertex cover we hope to find. In this case, \((G,k)\) is a yes-instance—belongs to our language \(\mathcal{L}\)—if and only if \(G\) has a vertex cover of size at most \(k\).

A formal language (parameterized decision problem) \(\mathcal{L} \subseteq \Sigma^* \times \mathbb{N}\) is fixed-parameter tractable (FPT) if there exists an algorithm that decides \(\mathcal{L}\) and runs in \(O(f(k) \cdot |x|^c)\) time for any input \((x,k) \in \Sigma^* \times \mathbb{N}\), where \(c\) is a constant and \(f\) is an arbitrary computable function.

We call an algorithm as in this definition a parameterized algorithm, fixed-parameter algorithm or, sometimes FPT algorithm (even though the algorithm itself is not fixed-parameter tractable, the problem it solves is). Our second goal in the following chapters is to study techniques for designing fast parameterized algorithms, ones that minimize \(f(k)\), for different problems. There is significant overlap with the techniques used to obtain fast exponential-time algorithms. We will use branching, dynamic programming, and inclusion-exclusion also to obtain parameterized algorithms. However, we will also study techniques that apply only to parameterized algorithms, namely kernelization and iterative compression.

The equivalence between decision problems and formal languages is the key to studying the computational complexity of problems, but in practice, we wouldn't be very happy with a simple yes/no answer. If the answer is "yes, \(G\) has a vertex cover of size \(k\)," we usually also want to know what such a vertex cover looks like. The decision algorithms in the following chapters always compute a solution (e.g., a vertex cover of size at most \(k\)) that proves that the input is a yes-instance if the answer is yes. For some of these algorithms, it is easier to describe them first in terms of looking for only a yes/no answer. It is then easy to verify that the algorithm is easily adapted to not only give this yes/no answer but produce a corresponding solution if the answer is yes.

Even being able to find a solution with objective function value at most \(k\), if such a solution exists, is not particularly useful by itself. We would have to guess an upper bound \(k\) on the objective function value of an optimal solution (e.g., on the size of an optimal vertex cover), and then the algorithm is guaranteed only to find a solution with objective function value at most \(k\). If our upper bound is far away from the objective function value of an optimal solution, we have no guarantee that the algorithm returns an optimal solution. Moreover, given that the running time of a parameterized algorithm depends (exponentially) on \(k\), if \(k\) is much larger than the parameter of an optimal solution, then the running time of the algorithm may deteriorate dramatically. This raises the question whether we can solve the optimization versions of parameterized decision problems in \(O(f(k^*) \cdot |x|^c)\) time, where \(k^*\) is the objective function value of an optimal solution. For example, we would like to find a minimum vertex cover \(C^*\) of a graph \(G\) in \(O(f(|C^*|) \cdot |G|^c)\) time. By the following lemma, we can do this if we can solve the parameterized decision version of the problem in \(O(f(k) \cdot |x|^c)\) time. Thus, this justifies our focus on parameterized decision problems in the following chapters.

Lemma 14.1: Let \(\Pi\) be a minimization problem with non-negative integral objective function values, let \(\textrm{OPT}(I)\) be the objective function value of an optimal solution for each instance \(I\) of \(\Pi\), and let \(\mathcal{L} = \{(I,k) \mid \textrm{OPT}(I) \le k\}\) be the language of all pairs \((I,k)\) such that \(I\) has a solution with objective function value at most \(k\). Assume further that there exists an algorithm \(\mathcal{D}\) that decides \(\mathcal{L}\) and runs in \(O(f(k) \cdot |I|^c)\) time for any input \((I,k)\). Finally, assume that given an instance \((I,k) \in \mathcal{L}\) as input, \(\mathcal{D}\) does not only answer yes but also produces a solution of \(\Pi\) on \(I\) with objective function value at most \(k\). Then if \(f\) is monotonically non-decreasing, there exists an algorithm \(\mathcal{O}\) that solves \(\Pi\) and runs in \(O(f(\textrm{OPT}(I)) \cdot \textrm{OPT}(I) \cdot |I|^c)\) time for any input \(I\). If \(f\) satisfies the stronger condition that \(\frac{f(k+1)}{f(k)} \ge a\) for all \(k \ge 0\) and some constant \(a > 1\), then \(\mathcal{O}\) runs in \(O(f(\textrm{OPT}(I)) \cdot |I|^c)\) time for any input \(I\). In particular, \(\mathcal{O}\) takes \(O(f(\textrm{OPT}(I)) \cdot |I|^c)\) time if \(f(k) = a^k\) for some constant \(a > 1\).

Proof: Consider an input \(I\) for which we want to find an optimal solution. Since \(\textrm{OPT}(I) \in \mathbb{N}\), we have \((I,\textrm{OPT}(I)) \in \mathcal{L}\) and \((I,k) \notin \mathcal{L}\) for all \(k < \textrm{OPT}(I)\). \(\mathcal{O}\) runs \(\mathcal{D}\) on instances \((I,0), (I,1), \ldots\) until it finds an instance \((I,k^*)\) for which \(\mathcal{D}\) answers yes and produces a solution of \(\Pi\) on \(I\) with objective function value at most \(k^*\). This is the solution that \(\mathcal{O}\) returns.

First note that \(k^* = \textrm{OPT}(I)\): We have \(k^* \ge \textrm{OPT}(I)\) because \(\mathcal{D}\) finds a solution of \(\Pi\) on \(I\) of objective function value at most \(k^*\) and \(\textrm{OPT}(I)\) is the minimum objective function value of any solution of \(\Pi\) on \(I\). We have \(k^* \le \textrm{OPT}(I)\) because for \(k = 0, 1, \ldots, k^* - 1\), \(\mathcal{D}\) answers that \((I,k) \notin \mathcal{L}\), so \(\textrm{OPT}(I) > k\) for all \(k < k^*\).

This in turn implies that the solution returned by \(\mathcal{O}\) is an optimal solution of \(\Pi\) on \(I\): Its objective function value is at most \(k^*\). Since there is no solution of \(\Pi\) on \(I\) with objective function value less than \(k^*\), the returned solution has objective function value exactly \(k^*\), which is equal to \(\textrm{OPT}(I)\), as just observed. This proves that \(\mathcal{O}\) correctly solves \(\Pi\) on any input \(I\).

Since \(\mathcal{O}\) runs \(\mathcal{D}\) on instances \((I,0), \ldots, (I,k^*) = (I,\textrm{OPT}(I))\), its running time is

\[\sum_{k=0}^{\textrm{OPT}(I)} O(f(k) \cdot |I|^c) = O(|I|^c) \cdot \sum_{k=0}^{\textrm{OPT}(I)} f(k).\]

If \(f\) is monotonically non-decreasing, then

\[\sum_{k=0}^{\textrm{OPT}(I)}f(k) \le \sum_{k=0}^{\textrm{OPT}(I)} f(\textrm{OPT}(I)) = (\textrm{OPT}(I) + 1) \cdot f(\textrm{OPT}(I)).\]

Thus,

\[O(|I|^c) \cdot \sum_{k=0}^{\textrm{OPT}(I)} f(k) = O(f(\textrm{OPT}(I)) \cdot \textrm{OPT}(I) \cdot |I|^c).\]

If \(f\) satisfies the stronger condition that \(\frac{f(k+1)}{f(k)} \ge a\) for all \(k \ge 0\) and some \(a > 1\), then

\[\sum_{k=0}^{\textrm{OPT}(I)}f(k) \le f(\textrm{OPT}(I)) \cdot \sum_{k=0}^{\textrm{OPT}(I)} \frac{1}{a^k} \le f(\textrm{OPT}(I)) \cdot \sum_{k=0}^\infty \frac{1}{a^k} = f(\textrm{OPT}(I)) \cdot \frac{a}{a - 1}.\]

Thus,

\[O(|I|^c) \cdot \sum_{k=0}^{\textrm{OPT}(I)} f(k) = O(f(\textrm{OPT}(I)) \cdot |I|^c).\ \text{▨}\]