8.3. Exponential-Time Algorithms

What if we do not want to settle for an approximation and instead insist on finding an optimal solution? In the case of the vertex cover problem, we want to find a vertex cover of minimum size. Given that the vertex cover problem is NP-hard, we should not hope to be able to find an optimal vertex cover in polynomial time unless \(\textrm{P} = \textrm{NP}\), that is, we have to accept that any exact algorithm for the vertex cover problem takes exponential time in the worst case. This gives rise to two natural questions:

The first question is analogous to the central question in designing classical polynomial-time algorithms: What is the fastest exponential-time algorithm we can design for a given NP-hard problem? For sorting, for example, an \(O(n \lg n)\)-time algorithm such as Merge Sort is preferable to an \(O\bigl(n^2\bigr)\)-time algorithm such as Insertion Sort, except for very small inputs. The gap between these two running times is a factor of \(\Theta\bigl(\frac{n}{\lg n}\bigr)\), which is rightly considered a significant improvement. However, this type of improvement pales in comparison to the types of improvements we can achieve for NP-hard problems by carefully designing exponential-time algorithms for these problem.

As an introductory example, we discuss three algorithms for the vertex cover problem below, two with running time \(O^*\bigl(2^n\bigr)\) and the other with running time \(O^*\bigl(1.619^n\bigr)\). When discussing exponential-time algorithms, we almost always write \(O^*(f(n))\) to denote running times of the form \(O(f(n) \cdot n^c)\), where \(f(n)\) is an exponential function. In other words, the \(O^*\)-notation ignores polynomial factors in the running time, which is justified because these polynomial factors are negligible in comparison to the exponential portion \(f(n)\) of the running time. How much of an improvement is a decrease of the algorithm's running time from \(O^*\bigl(2^n\bigr)\) to \(O^*\bigl(1.619^n\bigr)\)? Well, the gap is \(\bigl(\frac{2}{1.619}\bigr)^n \ge 1.235^n\), which dwarves the \(\Theta\bigl(\frac{n}{\lg n}\bigr)\) improvement achieved by Merge Sort in comparison to Insertion Sort. The point is that even seemingly small improvements in the base of the running time of exponential-time algorithms has a much greater impact on the running time of the algorithm than much more impressive-looking improvements in the running times of polynomial-time algorithms. Thus, it is worthwhile to look for the fastest possible exponential-time algorithms we can find for NP-hard problems.

The second question we ask about exponential-time algorithms is whether we can decouple the exponential explosion of their running times from the input size and instead make it depend only on some hardness parameter \(k\). We consider this question in the next section.

A Naïve Vertex Cover Algorithm and Exponential Branching

How quickly can we solve the vertex cover problem naïvely? Since a vertex cover is a subset of the vertices of \(G\), we can enumerate all \(2^n\) subsets of \(V\) and, for each, test whether it is a vertex cover, which takes \(O(m)\) time, constant time per edge. Thus, a naïve algorithm for the vertex cover problem takes \(O\bigl(2^n m\bigr) = O^*\bigl(2^n\bigr)\) time. Can we do better? As it turns out, we can. As a basis for this improvement, we first discuss one important technique for solving NP-hard problems efficiently: branching. We study this technique in greater detail in Chapter 16.

Consider an arbitrary edge \(e = (u,v)\). Any vertex cover has to contain at least one of its endpoints. If we include \(u\) in a vertex cover \(C\), then \(C \setminus {u}\) must be an optimal vertex cover for the subgraph \(G - u = G[V \setminus \{u\}]\)¹ because any vertex cover \(C'\) of \(G - u\) can be extended to a vertex cover \(C' \cup \{u\}\) of \(G\). Similarly, if we include \(v\) in a vertex cover \(C\), then \(C \setminus \{v\}\) must be an optimal vertex cover for the subgraph \(G - v\). Thus, we obtain the following simple recursive algorithm for finding a minimum vertex cover of a graph \(G = (V, E)\):

• If \(E = \emptyset\), then \(\emptyset\) is a vertex cover of \(G\) and no smaller vertex cover exists, so we return this vertex cover.
• If \(E \ne \emptyset\), then pick an arbitrary edge \((u,v) \in E\) and compute two optimal vertex covers \(C_u\) of \(G - u\) and \(C_v\) of \(G - v\). Return the smaller of \(C_u \cup \{u\}\) and \(C_v \cup \{v\}\).

We call this algorithm a branching algorithm because it "branches" on the possible choices of which endpoint of the edge \((u,v)\) to include in the vertex cover. For each choice, we end up with a different subproblem, which we solve by invoking the algorithm recursively.

Each recursive call is easily implemented in \(O(n)\) time. The two graphs \(G - u\) and \(G - v\) each have one less vertex than \(G\). Thus, the running time of this algorithm is given by the recurrence \(T(n) = O(n) + 2T(n-1)\), which is easily seen to have the solution \(T(n) = O\bigl(2^n n\bigr) = O^*\bigl(2^n\bigr)\).

Theorem 8.2: The vertex cover problem can be solved in \(O^*\bigl(2^n\bigr)\) time.

Improved Branching Rules

A common approach to designing fast exponential-time algorithms is to start with a simple and natural branching algorithm and then exploit insights into the structure of the problem to obtain better branching rules that lead to a lower fan-out or to a faster reduction of the input size in each branching step. The fan-out refers to the number of recursive calls that each invocation of the algorithm makes. The reduction of the input size refers to the sizes of the inputs of the recursive calls each invocation makes, relative to the input size of the current invocation. The simple branching algorithm for the vertex cover problem just discussed has fan-out \(2\), and the input of each recursive call has one vertex less than the input to the current invocation.

For the vertex cover problem, observe that there is some overlap between the two recursive calls in the branching algorithm in the previous section. The first vertex cover \(C_u \cup \{u\}\) we find is the smallest vertex cover that includes \(u\). The second vertex cover \(C_v \cup \{v\}\) is the smallest vertex cover that includes \(v\). However, the optimal vertex cover may include both \(u\) and \(v\). If this is the case, both recursive calls find the same vertex cover, at least potentially. This is redundant!

The problem is that the branching strategy was based on deciding which of the two endpoints of an edge to include in the vertex cover. A better strategy branches on the vertices, not edges, and decides for each vertex \(v\) whether to include it in the vertex cover or not. Again, if there are no edges, then the empty set is an optimal vertex cover. Thus, we can assume that the edge set is non-empty. We pick a vertex \(v\) of maximum degree. This vertex has degree at least \(1\). If \(v\) is in an optimal vertex cover \(C\), then \(C \setminus \{v\}\) is an optimal vertex cover of \(G - v\), just as in the edge-branching algorithm. If \(v\) is not in the vertex cover, then all of its neighbours must be in the vertex cover because all edges incident to \(v\) must be covered and we do not use \(v\) to cover them. Since the set of neighbours of \(v\), \(N(v)\), covers all edges incident to the vertices in \(N[v] = \{v\} \cup N(v)\), \(C \setminus N(v)\) must be an optimal vertex cover of the graph \(G - N[v] = G[V \setminus N[v]]\). We often refer to \(N(v)\) as the open neighbourhood of \(v\) and to \(N[v]\) as the closed neighbourhood of \(v\). This gives the following improved algorithm:

• If \(E = \emptyset\), return \(\emptyset\) as an optimal vertex cover of \(G\).
• If \(E \ne \emptyset\), then let \(v\) be a vertex of maximum degree. Recursively compute a vertex covers \(C_v\) of \(G - v\) and a vertex cover \(C_{N(v)}\) of \(G - N[v]\) and return the smaller of \(C_v \cup \{v\}\) and \(C_{N(v)} \cup N(v)\).

As before, \(G - v\) has \(n-1\) vertices. Since \(v\) has degree at least \(1\), we have \(|N[v]| \ge 2\), that is, \(G - N[v]\) has at most \(n-2\) vertices. Thus, the running time of this algorithm is given by the recurrence \(T(n) \le O(n) + T(n-1) + T(n-2)\), which has the solution \(T(n) = O^*\Bigl(\Bigl(\frac{1 + \sqrt{5}}{2}\Bigr)^n\Bigr) = O^*\bigl(1.619^n\bigr)\).

Theorem 8.3: The vertex cover problem can be solved in \(O^*\bigl(1.619^n\bigr)\) time.

Further careful improvements and better analysis techniques, discussed in Chapters 16 and 17, reduce this running time further.