Iterative compression

Iterative compression is an algorithmic technique invented by Reed, Smith and Vetta when they showed that the problem Odd Cycle Transversal was solvable in time O(3^k kmn). Odd Cycle Transversal was a longstanding central open question in parameterized complexity. This technique later proved very useful in showing fixed-parameter tractability results. It is now considered to be one of the fundamental techniques in the area of parameterized algorithmics.

Iterative compression has been used successfully in many problems, for instance odd cycle transversal (see below) and edge bipartization, feedback vertex set, cluster vertex deletion and directed feedback vertex set. It has also been used successfully for exact exponential time algorithms for independent set.

Technique

Suppose you have a graph problem with input a graph G = (V,E) and k, where k is a natural number. Suppose furthermore that you are looking for a solution X of vertices with |X| ≤ k, and that the problem is closed under induced subgraphs. In iterative compression, we are defining a compression variant of the problem, where we are given a solution Y which is too big, e.g., of size k + 1, and are asked to compress it to a solution of size k.

If we have such a compression variant of the problem, we can run the compression variant iteratively on larger induced subgraphs G₁ ⊂ G₂ ⊂ G₃ ⊂ ··· ⊂ G_n, where ⊂ denotes induced subgraphs, each time obtaining a compressed solution Y of size k, and then we add the newly introduced vertex to Y, leading to a solution of size k + 1. This allows us to run the compression algorithm again.

In total, this adds a linear factor overhead over the compression algorithm, so if the compression variant is solvable in fixed-parameter tractable time, i.e., f(k) · n^c for some constant c, then the iterative compression procedure solving the entire problem runs in f(k) · n^c+1 time.

Examples

In the original paper Reed et al. showed how to make a graph bipartite by deleting at most k vertices in time O(3^k kmn). Later, a simpler algorithm was given, also using iterative compression, by Lokshstanov, Saurabh and Sikdar. The technique they employed was to iteratively introduce new vertices to the deletion set Y, and in 3^k+1 time, "guess" a 3-partitioning Y_A, Y_B, Y_X of Y which meant that Y_A were the vertices of Y which should belong to the A-side of the bipartite graph, Y_B the vertices that should belong to the B-side and Y_X the vertices in Y that should remain deleted. This allowed the authors to run a max-flow min-cut algorithm to correctly compute the remaining vertices to delete.

Vertex cover is another example for which iterative compression can be employed. In the vertex cover problem, we are given a graph G = (V,E) and a natural number k and are asked to decide whether there exists a set X of vertices such that every edge is incident to a vertex in X. To see that this problem is fixed-parameter tractable, it is enough to observe that in the compression variant of the problem, we have a set Y of k + 1 vertices that are incident to all edges of the graph. Now we in 2^k+1 time guess which vertices will remain in the vertex cover and which vertices will be removed from the vertex cover and reintroduced back into the graph. Then what remains is to pick all the vertices that are incident to any edge which is not incident to the vertex cover. This gives a simple O(2^k n²) algorithm for vertex cover.

See also

• Algorithm
• Parameterized complexity
• Kernelization
• NP-hard
• Brute-force search
• Decision problem