20. Iterative Compression

Kernelization can be viewed as a way of focusing the search for a solution: We restrict the search to a problem kernel and then flesh it out to a solution on the full input. Iterative compression can be seen as another technique for focusing the search but, this time, without focusing on reducing the size of the input. Instead, we use a correct but possibly suboptimal solution to guide the search for an optimal solution. In most cases, we use a solution of size at most \(k+1\) to guide the search for a solution of size at most \(k\).

For graph problems, the general approach can be summarized as follows: Let \(V = \{v_1, \ldots, v_n\}\), let \(V_i = \{v_1, \ldots, v_i\}\), and let \(G_i = G[V_i]\). Then we iteratively find solutions for \(G_1, \ldots, G_n = G\). Given an optimal solution for \(G_i\), we use it to (straightforwardly) obtain a potentially suboptimal solution for \(G_{i+1}\) of size at most \(k+1\). Then we use this suboptimal solution for \(G_{i+1}\) to obtain an optimal solution for \(G_{i+1}\) of size at most \(k\) or conclude that no such solution exists. In the latter case, \(G\) does not have a solution of size at most \(k\) either. This construction of a size-\(k\) solution from a size-\((k+1)\) solution is the compression step from which this method derives its name. We apply \(n\) compression steps. Thus, if each step can be performed in \(O^*(f(k))\) time, the whole algorithm takes \(O^*(f(k))\) time.

We discuss this idea using vertex cover and feedback vertex set as examples. The resulting algorithm for vertex cover will not be competitive with the depth-bounded search algorithms we discussed before, as it will only achieve a running time of \(O^*(2^k)\). However, it serves as a good introductory example of the technique since the technical details are straightforward. The feedback vertex set algorithm is more illustrative of typical applications of the iterative compression technique in that it shows that proving that the compression step can be carried out in \(O^*(f(k))\) time can be quite challenging.