16. Branching Algorithms

This chapter focuses on branching algorithms to solve NP-hard problems. Mathematically, these algorithms are based on less exciting insights than clever kernelizations that play with deep structural properties of the problem, as we did in the previous chapter. From a practical point of view, however, branching algorithms are of much greater importance than kernelization results in the sense that a problem may have a very efficient solution based only on branching even though it is not known to have a small kernel, while a small kernel without an efficient branching algorithm often does not lead to particularly efficient algorithms. In practice, of course, if we have both a good kernelization algorithm and a branching algorithm for a given problem, we would expect to achieve the fastest possible running time by first computing a kernel and then applying the efficient branching algorithm to the kernel, provided that the kernelization is very effective in reducing the input size and computing the kernel does not take too long.

To illustrate these points, consider the vertex cover problem. We know how to compute a kernel of size \(2k\), and it can be shown that this is likely the best one can hope for. We already observed that the vertex cover problem can be solved in \(O^*(2^n)\) time. On a kernel of size \(2k\), the running time of this algorithm is \(O^*\bigl(2^{2k}\bigr) = O^*\bigl(4^k\bigr)\). If we want to improve on this running time, we have to improve the algorithm we apply to the kernel or use completely different approaches not based on kernelization. We observed in Chapter 8 that the vertex cover problem can be solved in \(O^*\bigl(2^k\bigr)\) time using only branching based on extremely simple branching rules. The best result obtainable using non-trivial extensions of these ideas achieves a running time of \(O^*\bigl(1.29^k\bigr)\). These algorithms do not use kernelization at all.

The conceptual simplicity of branching algorithms can also be viewed as a positive of these algorithms because it makes them relatively easy to implement and use in practice.

The roadmap for this chapter is as follows:

• In Section 16.1, we introduce the basic idea of branching using two problems as examples: vertex cover and independent set. While we discussed an \(O^*(2^n)\)-time branching algorithm for the vertex cover problem already in Section 8.3, we revisit it here to illustrate two key tools for the analysis of branching algorithms: branching vectors and branching numbers. Essentially the same algorithm can be used to solve the independent set problem.

• The next technique we introduce is depth-bounded search, which allows us to obtain branching algorithms with FPT running times. In Section 8.4, we already discussed how to obtain an \(O^*\bigl(2^k\bigr)\)-time algorithm for the vertex cover problem. In Section 16.2, we illustrate this technique further using cluster editing, closest string, and satisfiability as examples.

• The third part of this chapter (Sections 16.3 and 16.4) discusses two techniques for obtaining faster branching algorithms: better branching rules and combining recursive calls. The idea of the former technique, illustrated using the vertex cover and independent set problems, is to use structural insights into the problem to design branching rules that make fewer recursive calls or make faster progress towards a solution in some branches, thereby reducing the running time of the algorithm. A simple example of this approach was already discussed in Section 8.3. The idea of the latter technique, illustrated using cluster editing and the vertex cover problem, is that the worst case assumed by a naïve analysis cannot arise in all recursive calls: If one invocation makes many recursive calls, then we can use this to eliminate some branches in the recursive calls it makes. Again, this reduces the size of the recursion tree and thus leads to a faster algorithm.