16.4. Combining Recursive Calls

The basic idea of analyzing the interaction between sequences of recursive calls is to argue that, while some invocations may make many recursive calls and achieve only relatively small reductions in the input size or parameter in each recursive call, this cannot go on forever and must eventually be followed by a more favourable invocation that either makes few recursive calls or achieves a more dramatic reduction in the input size or parameter. Together, these invocations thus achieve a better branching vector than the combination of only worst-case invocations.

While this idea applies to both exact exponential and FPT branching algorithms, we use two FPT algorithms as examples in this section. So far we showed how to obtain algorithms with running times of \(O^*\bigl(3^k\bigr)\) and \(O^*\bigl(1.62^k\bigr)\) for cluster editing and vertex cover, respectively. In this section, we improve these bounds to \(O^*\bigl(2.27^k\bigr)\) and \(O^*\bigl(1.33^k\bigr)\), respectively.