16.1.2. Branching Numbers and Branching Vectors

Next we use the simple branching algorithm for the vertex cover problem to introduce branching numbers and branching vectors and illustrate how they can be used to analyze the running times of branching algorithms.

If every invocation of a branching algorithm on an input of size \(n\) that makes any recursive calls at all makes \(t\) recursive calls with input sizes bounded by \(n - b_1, \ldots, n - b_t\), we say that the algorithm has the branching vector \((b_1, \ldots, b_t)\).

In order to ensure that the algorithm does not run forever by recursing on the same input over and over again, we need that \(b_i > 0\) for all \(1 \le i \le t\). We will also assume that \(t \ge 2\) because otherwise the algorithm does not really branch and we can collapse any sequence of recursive calls made without branching into a single recursive call by using iteration instead of recursion.

The key observation for analyzing the running times of branching algorithms is the following:

Observation 16.2: A branching algorithm with branching vector \((b_1, \ldots, b_t)\) makes \(O(c^n)\) recursive calls where \(b = \max\{b_1, \ldots, b_t\}\) and \(c\) is the smallest real root of the polynomial \(x^b - \sum_{i=1}^t x^{b - b_i}\). We call \(c\) the branching number of the algorithm.

Proof: Consider the tree \(R\) of recursive calls made by the algorithm. Since every invocation that does recurse makes at least two recursive calls, the number of internal nodes of \(R\) is at most the number of leaves of \(R\). It thus suffices to prove that the number of leaves of \(R\) is at most \(c^n\).

If \(n\) is the input size of the root invocation of \(R\), then the number of leaves of \(R\) is given by the recurrence

\[L(n) \le \sum_{i=1}^t L(n - b_i) \le \sum_{i=1}^t L(n - 1) = t^n.\]

This shows that a constant \(c > 0\) with \(L(n) \le c^n\) exists (assuming \(t\) is a constant, which is true for all algorithms considered in this chapter, except for the closest string problem). Since

\[L(n) \le \sum_{i=1}^t L(n - b_i),\]

substituting \(c^m\) for every \(L(m)\) term gives

\[c^n \le \sum_{i=1}^t c^{n - b_i}.\]

By dividing this inequality by \(n - b\) and converting it to an equality to reflect the worst case, we obtain

\[\begin{aligned} c^b &= \sum_{i=1}^t c^{b - b_i}\\ c^b - \sum_{i=1}^t c^{b - b_i} &= 0.\ \text{▨} \end{aligned}\]

As a first application of Observation 16.2, use it to bound the running time of the simple minimum vertex cover algorithm above.

Corollary 16.3: The simple branching algorithm for computing a minimum vertex cover given in this section has running time \(O^*(2^n)\).

Proof: Given an input graph \(G\), the algorithm does not make any recursive calls if \(G\) has no edges. Otherwise, it makes recursive calls on the two graphs \(G - v\) and \(G - N[v]\). Since both graphs have at most \(n-1\) vertices, the branching vector of the algorithm is \((1, 1)\), which means the algorithm's branching number \(c\) is the smallest real root of the polynomial \(c - 1 - 1\), that is, \(c = 2\). Thus, the algorithm makes \(O(2^n)\) recursive calls. Since each recursive call is easily seen to take \(O(n + m)\) time, the algorithm thus takes \(O(2^n(n + m)) = O^*(2^n)\) time. ▨

In our definition of the the branching vector, we assumed that every invocation that makes any recursive calls makes exactly \(t\) recursive calls, on inputs of size \(n - b_1, \ldots, n - b_t\). More sophisticated algorithms, such as the ones we discuss later in this chapter, apply different branching rules depending on the structure of the input. Thus, different recursive calls may make different numbers of recursive calls, on inputs of different sizes. We analyze such algorithms by determining the branching vector for each branching rule and computing the corresponding branching number for each branching vector using Observation 16.2. The worst-case running time of the algorithm arises when every invocation applies the branching rule with the highest branching number \(c\). This gives an upper bound of \(O^*(c^n)\) on the running time of the algorithm.