14. Introduction to Exponential-Time Algorithms

In Chapters 9–13, we focused on the question whether NP-hard optimization problems can be approximated in polynomial time and how well. In the following chapters, we will focus on solving NP-hard problems exactly. This will necessarily require the developed algorithms to take exponential time in the worst case. However, just as a linear-time algorithm is better than a quadratic-time algorithm for a problem that can be solved in polynomial time, an \(O\bigl(2^n\bigr)\)-time algorithm is better than an \(O\bigl(4^n\bigr)\)-time or \(O(n!)\)-time algorithm for an NP-hard problem. Thus, our goal in the following chapters is to study techniques for developing exponential-time algorithms for NP-hard problems that are as fast as possible.

This is more than a theoretical exercise. There are numerous application areas where approximations are not very useful. For example, when trying to discover certain events in the evolutionary history of a set of species, computing a set of such events that is up to a constant factor larger than the true answer is generally considered to be of little use. Thus, exact solutions or very good approximations are needed. "Very good" usually means a \((1+\epsilon)\)-approximation. However, most (F)PTASs have an exponential or large polynomial dependence on \(\epsilon\). Thus, such approximation algorithms are often no more efficient than exponential-time algorithms that guarantee an exact answer.

Another argument in favour of exponential-time algorithms is that many computer scientists have come to realize that the traditional approach of modelling the running time of an algorithm as a function of only the input size sheds too little light on the computational difficulty of a problem on a particular input. Consider Insertion Sort. In the worst case, it runs in \(O\bigl(n^2\bigr)\) time; on an already sorted input, it takes linear time. Thus, there exist hard and easy inputs for Insertion Sort (even though most inputs are hard) and the hardness of an input is determined by its structure rather than the input size. Similarly, numerous NP-hard problems have large easy instances and small hard instances. Thus, it is reasonable to ask whether an NP-hard problem can be solved in time polynomial in its input size and exponential in some hardness parameter. In this case, the problem is called fixed-parameter tractable: For a fixed hardness parameter, the running time is polynomial in the input size; the problem becomes tractable. In practice, this means that if we have evidence that the hardness parameter is small for the input instances we expect to encounter in real-world expectations, then we can often solve such problems very efficiently, in a fraction of a second for some problems, even though the problem is NP-hard.