14.3. Roadmap

The roadmap for the discussion of exponential-time algorithms is as follows:

• We start, in Chapter 15, by discussing data reductions and kernelization. The idea of data reduction is to apply rules that allow us to "peel away the easy part" of the input, in polynomial time. What's left is the hard core of the problem, for which we need to spend exponential time to find an optimal solution. If this hard core is much smaller than the original input, then the resulting algorithm is much faster than running some exponential-time algorithm on the original input.

  Whenever we can devise good data reduction rules for some problem, they are often very useful in practice, even if we cannot prove anything about the size of the "hard core" of the problem we are left with once the data reduction rules can no longer be applied. We call these rules a kernelization and the "hard core" the problem kernel if we can prove that the size of this hard core depends only on the hardness parameter \(k\) of the input instance \((I, k)\). In this case, we obtain a parameterized algorithm for the problem simply by applying the kernelization and then solving the problem on the kernel using any arbitrary exponential-time algorithm.

  This connection between kernelization and fixed-parameter tractability goes deeper: We will show that a problem is fixed-parameter tractable if and only if it has a kernel. However, the proof of this fact will not shed any light on how to obtain a good kernel, one of small size.

• In practice, the most important technique for solving NP-hard problems is probably branching, which we discuss in Chapter 16. This technique is applicable whenever we can obtain a solution of the problem by making "elementary decisions", each of which involves choosing from a small number of possible choices. For example, we can obtain a vertex cover of a graph by deciding for every vertex whether to include it in the vertex cover or not. For each vertex, we have exactly two choices: to include it in the vertex cover or not. For such problems, we can pick one elementary decision to be made. We know that one of the choices must be the correct one, one that leads to an optimal solution of the problem, but we do not know which one. So we consider every possible choice and recursively solve the subproblem we obtain after making this choice. The solution produced by the recursive call with the best solution must be the optimal solution, which we return.

  The key to obtaining fast branching algorithms is to identify the right kind of elementary decision to be made. For the vertex cover problem, the simple decision whether to include a vertex in the vertex cover or not leads to an \(O^*\bigl(2^n)\bigr)-time algorithm. By considering larger (but still constant-size) subgraphs and deciding for each which subset of vertices to include in the solution, we can obtain significantly faster algorithms.

  For a number of problems, we can guarantee that the recursion depth of this recursive search for an optimal solution is bounded not by the input size but by the hardness parameter if we want to solve the parameterized version of the problem. In this case, the total number of recursive calls the algorithm makes is some function of the parameter. If each invocation takes polynomial time, we thus obtain a parameterized algorithm for the problem.

• In Chapter 17, we discuss measure and conquer. I already outlined the main idea above. It is a technique for analyzing the running times of branching algorithms. We first define an appropriate parameter associated with every input instance and then derive a bound on the running time of the algorithm in terms of this parameter. We then establish a bound on the parameter as a function of the input size and substitute this bound into the running time bound we have obtained so far. This gives us a bound on the running time of the algorithm in terms of the input size.

  Note that there is no assumption that the parameter is small here. We accept that this parameter may depend on the input size, but we can prove some bound on the paramater as a function of the input size. It turns out that the right choice of parameter can lead to much better bounds on the running time of an algorithm compared to what one would obtain using a direct analysis of the algorithm in terms of the input size. Intuitively, the reason is that, just as the parameter \(k\) in a parameterized problem, the parameter captures some structural properties of the input that make the input hard to solve. After making a difficult elementary decision, the remaining input may become easier to solve, which may not be reflected adequately in the size of the remaining input we recurse on, but the parameter captures it.

• You are familiar with dynamic programming from CSCI 3110. Whenever an optimal solution of a problem on a given input is composed of optimal solutions of the same problem on smaller inputs—we called this optimal substructure in CSCI 3110—we can build a table of optimal solutions of all possible subproblems we may have to consider and then use lookups in this table to find an optimal solution quickly. The key to obtaining a polynomial-time algorithm is that the number of subproblems we need to consider is only polynomial in the input size. If the number of subproblems is exponential, the resulting algorithm runs in exponential time.

  Problems where dynamic programming is effective to obtain fast polynomial-time algorithms are the ones where a simple recursive algorithm (a branching algorithm) would make an exponential number of recursive calls, many of which solve the exact same subproblem over and over again. By storing the solutions to these subproblems in a table, we can lookup the solutions we have already computed without computing them from scratch again. This reduces the cost of the algorithm to polynomial if the total number of subproblems is polynomial.

  Even if the number of subproblems we have to consider is exponential, this number may be much smaller than the number of recursive calls made by a simple branching algorithm for the problem. Thus, dynamic programming can also be used as a speed-up technique for exponential-time algorithms, both for algorithms whose running time depends exponentially on the input size and for parameterized algorithms. This is what we discuss in Chapter 18.

• A major drawback of dynamic programming, especially in the context of exponential-time algorithms, is the amount of space it uses: It needs to store the solution to every possible subproblem in a table. If this table has exponential size, then the algorithm uses exponential space. Modern computers have extremely fast CPUs. In comparison, the amount of memory they have is rather limited. If you use an exponential-space algorithm, this algorithm will run out of memory fairly quickly even if you have 1TB of RAM.

  Thus, it is desirable to obtain exponential-time algorithms that use only polynomial space. Branching algorithms usually have this property, but they do not take advantage of overlapping subproblems the way dynamic programming does. So it seems that there is a trade-off between time and space: If we want a faster algorithm, we have to pay for this speed-up by using more space. This is a fairly common phenomenon. For some problems, however, we can do better: We can combine the type of speed-up achievable using dynamic programming with using only polynomial space.

  The technique to achieve this is inclusion-exclusion, which we discuss in Chapter 19. This is in fact a technique used in combinatorics to count the number of combinatorial structures with a particular set of properties. The basic principle is simple. Let \(A\) be the set of structures with one property, and let \(B\) be the set of structures with another property. Then the set of objects that have both properties is \(A \cap B\). To determine the number of objects that have both properties, we need to determine \(|A \cap B|\). It may be much easier to count how many objects have at least one of the properties, how many objects have the first property, and how many objects have the second property. These are just the size of the sets \(A \cup B\), \(A\), and \(B\). Inclusion-exclusion then tells us that

  \[|A \cap B| = |A| + |B| - |A \cup B|.\]

  It turns out, we can use it construct fast polynomial-space algorithms for NP-hard problems. As an example, consider the Hamiltonian cycle problem: The question is whether a given graph \(G\) has a Hamiltonian cycle, a simple cycle that visits all vertices. If it does, then we would like to find such a cycle. To decide whether \(G\) has a Hamiltonian cycle, we can count how many Hamiltonian cycles there are in \(G\). \(G\) has a Hamiltonian cycle if and only if this count is positive. It turns out that the tabulation necessary to solve this problem using inclusion-exclusion uses only polynomial space.

• The final techniques we discuss is probably my favourite technique for obtaining parameterized algorithms, even though it seems less widely applicable than branching algorithms. The idea is simple: Assume we are given a parameterized instance \((I,k)\), where the parameter \(k\) measures the quality of the solution, and a solution for \(I\) whose parameter is \(k'\). If \(k'\) isn't much bigger than \(k\), say \(k' = k + 1\), does this solution help us decide whether there exists a solution with parameter only \(k\) and, if so, find one? It turns out that the answer is yes for some problems, and the resulting algorithms are rather elegant (but not as fast as branching algorithms for the same problems). We discuss this technique in Chapter 20.