17. Measure and Conquer

Our analysis of exponential branching algorithms so far has focused on showing that each branch decreases the input size by a certain amount, which leads to a running time of \(O^*(c^n)\) if each branching rule makes only a constant number of recursive calls. We have also seen that the input size may be a too crude measure of the difficulty of an input and have seen that the exponential explosion of the running time can often be restricted to some hardness parameter \(k\).

Measure and Conquer is an analysis technique for obtaining running times of the form \(O^*(c^n)\) but with smaller constants \(c\) than are obtainable by considering the input sizes of the different recursive calls the algorithm makes. Similar to parameterized algorithms, the idea is that some parts of the input are harder to deal with than others and thus contribute to different degrees to the running time of the algorithm. Measure and Conquer is also similar to the technique for obtaining better branching rules by analyzing how subsequent invocations are influenced by choices made in the current invocation. A fundamental difference is that these interactions are exploited purely at an analytical level, without changing the algorithm.

In more concrete terms, when using the Measure and Conquer technique, we assign weights to different parts of the input that capture how difficult each part of the input is to deal with. The weight of the whole input is the sum of the weights of its parts. The analysis then considers how each recursive call of a branching rule decreases the weight of the input rather than its size. This produces a branching vector with respect to the weight of the input instead of its size and thus gives a running time of the form \(O^*\bigl(c^W\bigr)\), where \(W\) is the weight of the input. The final step then is to bound the weight of the input in terms of its size to obtain a running time of the form \(O^*(d^n)\) again.

We illustrate this technique using the maximum independent set problem, the feedback vertex set problem, the dominating set problem, and the set cover problem as examples in this chapter.