Iterative compression

Iterative compression is an algorithmic technique invented by Reed, Smith and Vetta[1] to show that the problem Odd Cycle Transversal was solvable in time O(3k kmn). Odd Cycle Transversal was a longstanding central open question in parameterized complexity.[2] 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.[3] It has also been used successfully for exact exponential time algorithms for independent set.[4]

Technique

Consider a graph problem whose inputs are a graph G = (V,E) and a natural number k. Suppose furthermore that the solution X of vertices has the constraint |X| ≤ k, and that the problem is closed under induced subgraphs. In iterative compression, a compression variant of the problem is one where a solution Y of size k + 1 must be compressed to a solution of size k.

If there exists a compression variant of the problem it can be applied iteratively on larger induced subgraphs G1 ⊂ G2 ⊂ G3 ⊂ ··· ⊂ Gn, where ⊂ denotes induced subgraphs, each time obtaining a compressed solution Y of size k. Then the newly introduced vertex is added to Y, leading to a solution of size k + 1. This allows the compression algorithm to be applied again.

In total, this adds a linear factor overhead over the compression algorithm. Therefore, if the compression variant is solvable in fixed-parameter tractable time, i.e., f(k) · nc for some constant c, then the iterative compression procedure solving the entire problem runs in f(k) · nc+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(3k kmn). Later, a simpler algorithm was given, also using iterative compression, by Lokshstanov, Saurabh and Sikdar.[5] The technique they employed was to iteratively introduce new vertices to the deletion set Y, and in 3k+1 time, "guess" a 3-partitioning YA, YB, YX of Y which meant that YA were the vertices of Y which should belong to the A-side of the bipartite graph, YB the vertices that should belong to the B-side and YX 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, a graph G = (V,E) and a natural number k are taken as inputs and the algorithm must 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 there is a set Y of k + 1 vertices that are incident to all edges of the graph. In 2k+1 time the algorithm guesses the vertices will remain in the vertex cover and which vertices will be removed from the vertex cover and reintroduced back into the graph. 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(2k n2) algorithm for vertex cover.

See also

References

  1. ↑ Reed, Bruce; Smith, Kaleigh; Vetta, Adrian (2004), "Finding odd cycle transversals", Operations Research Letters 32 (4): 299–301, doi:10.1016/j.orl.2003.10.009, MR 2057781
  2. ↑ Niedermeier, Rolf. Invitation to Fixed-Parameter Algorithms. Oxford University Press. p. 184. ISBN 9780198566076.
  3. ↑ Guo, Jiong; Moser, Hannes; Niedermeier, Rolf (2009), "Iterative compression for exactly solving NP-hard minimization problems", Algorithmics of Large and Complex Networks: 65–80, doi:10.1007/978-3-642-02094-0_4
  4. ↑ Fomin, Fedor; Gaspers, Serge; Kratsch, Dieter; Liedloff, Mathieu; Saurabh, Saket (2010), "Iterative compression and exact algorithms", Theoretical Computer Science 411 (7): 1045–1053, doi:10.1016/j.tcs.2009.11.012
  5. ↑ Lokshtanov, Daniel; Saurabh, Saket; Sikdar, Somnath (2009), "Simpler parameterized algorithm for OCT", Combinatorial algorithms 5874: 380–384, doi:10.1007/978-3-642-10217-2_37