14.1. Exact Exponential Algorithms

The goal of exact exponential algorithms is to solve NP-hard problems in \(O^*(f(n))\) time, where \(f(n)\) is an exponential function and we try to make this function as small as possible. Conceptually, this is all there is to it. The key question we will consider in the following chapters is what techniques we have at our disposal to minimize \(f(n)\). We will study branching algorithms, the inclusion-exclusion technique, dynamic programming, and measure & conquer as the key techniques for designing efficient exponential-time algorithms. The gem in this list is measure & conquer. This is not in fact an algorithm design technique but an algorithm analysis technique. It is somewhat akin to fixed-parameter algorithms in the sense that it defines some parameter of the input and expresses the running time as a function of this parameter. In contrast to fixed-parameter algorithms, the parameter used in measure & conquer is related to the input size. By analyzing the running time of the algorithm in terms of the parameter and then converting the resulting bound into a function of the input size, we obtain a better bound than if we analyzed the running time directly in terms of the input size.