16.2. Depth-Bounded Search

The branching algorithms we have discussed so far all have a running time of the form \(O^*(c^n)\), where \(c > 1\) is some constant. As such, these are not parameterized algorithms, even though we can turn at least the vertex cover algorithm into a parameterized algorithm by applying it to a problem kernel obtained using one of the kernelization algorithms from the previous chapter. For the maximum independent set problem, this strategy is unlikely to work because the maximum independent set problem is \(W[1]\)-hard when parameterized by the size of the maximum independent set. Just as an NP-hard problem cannot be solved in polynomial time unless \(\textrm{P} = \textrm{NP}\), a \(W[h]\)-hard problem is not FPT unless some fundamental complexity-theoretic assumptions fail. There is a whole hierarchy of these hardness classes. A \(W[2]\)-hard problem is "farther away" from being FPT than a problem in \(W[1]\). We do not discuss these complexity-theoretic underpinnings here. It suffices to know that a \(W[h]\)-hard problem is unlikely to be FPT in the same sense that an NP-hard problem is unlikely to be solvable in polynomial time.

Our goal in this section is to obtain branching algorithms for the vertex cover problem, as well as the cluster editing and the closest string problems, with running time \(O^*\bigl(c^k\bigr)\), where \(k\) is the size of the computed vertex cover, the number of edge edits required to turn \(G\) into a cluster graph or the maximum Hamming distance between the set of input strings and the computed consensus string in the closest string problem. These algorithms achieve these running times directly, without relying on kernelization.