Iterative compression

Last updated November 25, 2023

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 of odd cycle transversal was solvable in time $O (3 k kmn)$ , for a graph with $n$ vertices, $m$ edges, and odd cycle transversal number $k$ . Odd cycle transversal is the problem of finding the smallest set of vertices of a graph that includes 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 $\leq k$ . Suppose that the problem has the following properties:

It is closed under induced subgraphs: If a solution of size $\leq k$ exists in a given graph, then a solution of this size or smaller also exists in every induced subgraph).
If $X$ is a solution, and $X'$ is a set of vertices containing $X$ , then $X'$ is also a solution.
There exists an efficient subroutine which, given a solution $Y$ of size $k + 1$ determines whether it can be compressed to a solution of size $k$ . That is, it finds a solution of size $k$ or determines that no such solution exists.

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:

Start with a subgraph induced by a vertex set $S$ of size $k$ , and a solution $X$ that equals $S$ itself. (If $X$ is not a solution to $S$ then no solution exists.)
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 \cup {v$ } 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) · n^c for some constant c, then the iterative compression procedure solving the entire problem runs in f(k) · n^c+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 their 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.^[6] In order to compress a deletion set $Y$ of size $k + 1$ to a deletion set $X$ of size $k$ , their algorithm tests all of the $3 k +1$ partitions of $Y$ into three subsets: the subset of $Y$ that belongs to the new deletion set, and the two subsets of $Y$ that belong to the two sides of the bipartite graph that remains after deleting $X$ . Once these three sets have been selected, the remaining vertices of a deletion set $X$ (if it exists) can be found from them by applying a max-flow min-cut algorithm.

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 $k$ vertices such that every edge is incident to a vertex in $X$ . In the compression variant of the problem, the input is a set $Y$ of $k + 1$ vertices that are incident to all edges of the graph, and the algorithm must find a set $X$ of size $k$ with the same property, if it exists. One way to do this is to test all $2 k + 1$ choices of which subset of $Y$ is to be removed from the cover and reintroduced back into the graph. Such a choice can only work if no two removed vertices are adjacent, and for each such choice, the subroutine must include in the cover all the vertices outside $Y$ that are incident to an edge that becomes uncovered by this removal. Using this subroutine in an iterative compression algorithm gives a simple $O (2 k n 2)$ algorithm for vertex cover.

Related Research Articles

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets $and, that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.$

In computer science, the clique problem is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well-known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non-negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals and minimizes the total weight of its edges. Further well-known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem.

In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured as a function of the number of bits in the input. This appears to have been first demonstrated in Gurevich, Stockmeyer & Vishkin (1984). The first systematic work on parameterized complexity was done by Downey & Fellows (1999).

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

In graph theory, a cograph, or complement-reducible graph, or P₄-free graph, is a graph that can be generated from the single-vertex graph K₁ by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K₁ and is closed under complementation and disjoint union.

<span class="mw-page-title-main">Dominating set</span> Subset of a graphs nodes such that all other nodes link to at least one

In graph theory, a dominating set for a graph $G$ is a subset $D$ of its vertices, such that any vertex of $G$ is either in $D$ , or has a neighbor in $D$ . The domination number $γ(G)$ is the number of vertices in a smallest dominating set for $G$ .

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing a directed acyclic graph, an acyclic subgraph of the given graph. The feedback arc set with the fewest possible edges is the minimum feedback arc set and its removal leaves the maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

In graph theory, a connected dominating set and a maximum leaf spanning tree are two closely related structures defined on an undirected graph.

In graph theory, the Grundy number or Grundy chromatic number of an undirected graph is the maximum number of colors that can be used by a greedy coloring strategy that considers the vertices of the graph in sequence and assigns each vertex its first available color, using a vertex ordering chosen to use as many colors as possible. Grundy numbers are named after P. M. Grundy, who studied an analogous concept for directed graphs in 1939. The undirected version was introduced by Christen & Selkow (1979).

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

In computer science, a kernelization is a technique for designing efficient algorithms that achieve their efficiency by a preprocessing stage in which inputs to the algorithm are replaced by a smaller input, called a "kernel". The result of solving the problem on the kernel should either be the same as on the original input, or it should be easy to transform the output on the kernel to the desired output for the original problem.

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

<span class="mw-page-title-main">Maximum cut</span> Problem of finding a maximum cut in a graph

For a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets $S$ and $T$ , such that the number of edges between $S$ and $T$ is as large as possible. Finding such a cut is known as the max-cut problem.

Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the graph minor theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos, for which the authors received the Nerode Prize in 2015.

In graph theory, a branch of mathematics, a $t$ -biclique-free graph is a graph that has no $2t$ -vertex complete bipartite graph $K t, t$ as a subgraph. A family of graphs is biclique-free if there exists a number $t$ such that the graphs in the family are all $t$ -biclique-free. The biclique-free graph families form one of the most general types of sparse graph family. They arise in incidence problems in discrete geometry, and have also been used in parameterized complexity.

In graph theory, a branch of mathematics, a half graph is a special type of bipartite graph. These graphs are called the half graphs because they have approximately half of the edges of a complete bipartite graph on the same vertices. The name was given to these graphs by Paul Erdős and András Hajnal.

In graph theory, an odd cycle transversal of an undirected graph is a set of vertices of the graph that has a nonempty intersection with every odd cycle in the graph. Removing the vertices of an odd cycle transversal from a graph leaves a bipartite graph as the remaining induced subgraph.

References

↑ 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 .
↑ Niedermeier, Rolf, Invitation to Fixed-Parameter Algorithms, Oxford University Press, p. 184, ISBN 9780198566076
↑ 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 .
↑ Guo, Jiong; Moser, Hannes; Niedermeier, Rolf (2009), "Iterative compression for exactly solving NP-hard minimization problems", Algorithmics of Large and Complex Networks, Lecture Notes in Computer Science, vol. 5515, Springer, pp. 65–80, doi:10.1007/978-3-642-02094-0_4, ISBN 978-3-642-02093-3 .
↑ 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 .
↑ Lokshtanov, Daniel; Saurabh, Saket; Sikdar, Somnath (2009), "Simpler parameterized algorithm for OCT", 20th International Workshop on Combinatorial Algorithms, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28–July 2, 2009, Revised Selected Papers, Lecture Notes in Computer Science, vol. 5874, Springer, pp. 380–384, doi:10.1007/978-3-642-10217-2_37, ISBN 978-3-642-10216-5 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[reed2004finding-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] 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 .

[guo2009iterative-4] Guo, Jiong; Moser, Hannes; Niedermeier, Rolf (2009), "Iterative compression for exactly solving NP-hard minimization problems", Algorithmics of Large and Complex Networks, Lecture Notes in Computer Science, vol. 5515, Springer, pp. 65–80, doi:10.1007/978-3-642-02094-0_4, ISBN 978-3-642-02093-3 .

[fomin2010iterative-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 .

[lokshtanov2009simpler-6] Lokshtanov, Daniel; Saurabh, Saket; Sikdar, Somnath (2009), "Simpler parameterized algorithm for OCT", 20th International Workshop on Combinatorial Algorithms, IWOCA 2009, Hradec nad Moravicí, Czech Republic, June 28–July 2, 2009, Revised Selected Papers, Lecture Notes in Computer Science, vol. 5874, Springer, pp. 380–384, doi:10.1007/978-3-642-10217-2_37, ISBN 978-3-642-10216-5 .

[1]

[2]

[3]

[4]

[5]

[6]

Iterative compression

Contents

Technique

Applications

See also

Related Research Articles

References