Jump to content

Iterative compression

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by David Eppstein (talk | contribs) at 00:06, 21 January 2016 (→Technique: more). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In computer science, iterative compression is an algorithmic technique for the design of fixed-parameter tractable algorithms, in which one element (such as a vertex of a graph) is added to the problem in each step, and a small solution for the problem prior to the addition is used to help find a small solution to the problem after the step.

The technique was invented by Reed, Smith and Vetta[1] to show that the problem odd cycle transversal was solvable in time O(3k kmn), for a graph with n vertices, m edges, and odd cycle traversal number k. Odd cycle transversal is the problem of finding the smallest set of vertices of a graph that include at least one vertex from every odd cycle; its parameterized complexity was a longstanding open question.[2][3] 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.[4] It has also been used successfully for exact exponential time algorithms for independent set.[5]

Technique

Iterative compression applies, for instance, to parameterized graph problems whose inputs are a graph G = (V,E) and a natural number k, and where the problem is to test the existence of a solution (a set of vertices) of size ≤ k. Suppose that the problem is closed under induced subgraphs (if a solution of size ≤ k exists in a given graph, then a solution of this size or smaller also exists in every induced subgraph) and that there exists an efficient subroutine that determines whether a solution Y of size k + 1 can be compressed to a smaller solution of size k.

If these assumptions are met, then the problem can be solved by adding vertices one at a time to an induced subgraph, and finding the solution to the induced subgraph, as follows:

  1. Start with a subgraph induced by a vertex set S of size k, and a solution X that equals S itself.
  2. While S ≠ V, perform the following steps:
    • Let v be any vertex of V \ S, and add v to S
    • Test whether the (k + 1)-vertex solution Y = X ∪ {x} to S can be compressed to a k-vertex solution.
    • If it cannot be compressed, abort the algorithm: the input graph has no k-vertex solution.
    • Otherwise, set X to the new compressed solution and continue the loop.

This algorithm calls the compression subroutine a linear number of times. 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. The same technique can be applied to finding sets of edges for graph properties closed under subgraphs (rather than induced subgraph), or for other properties beyond graph theory. When the value of the parameter k is unknown, it can be found by using an outer level of exponential search or sequential search for the optimal choice of k, with each step of the search based on the same iterative compression algorithm.

Applications

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.[6] 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. {{cite book}}: |access-date= requires |url= (help)
  3. ^ Cygan, Marek; Fomin, Fedor V.; Kowalik, Lukasz; Lokshtanov, Daniel; Marx, Daniel; Pilipczuk, Marcin; Pilipczuk, Michal; Saurabh, Saket (2015). Parameterized Algorithms. Springer. p. 555. ISBN 978-3-319-21274-6.
  4. ^ 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
  5. ^ 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
  6. ^ 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
Retrieved from "https://en.wikipedia.org/w/index.php?title=Iterative_compression&oldid=700846783"