Other meanings of Iterative compression
Computer Science
Iterative compression is a technique in parameterized complexity theory for designing fixed-parameter tractable (FPT) algorithms. It works by starting with a solution that is slightly too large and then repeatedly compressing it to a smaller valid solution until the target size is reached. The method was introduced by Reed, Smith, and Vetta in 2004 for the odd cycle transversal problem and has since become a standard tool in the field.
Iterative compression is a technique for designing fixed-parameter tractable (FPT) algorithms, where the running time is polynomial in the input size but exponential only in a parameter k. The approach assumes that a solution of size k+1 is already known; the algorithm then tries to find a solution of size k by examining all possible ways to modify the larger solution. This is typically done by partitioning the larger solution into two parts: one that is kept and one that is discarded, and then solving a smaller, often polynomial-time solvable, subproblem on the remaining graph.1
The technique was first explicitly formulated by Reed, Smith, and Vetta in 2004 in their paper on odd cycle transversal, where they achieved a running time of O(3k·n·m).2 Since then, it has been applied to many problems, including feedback vertex set, cluster vertex deletion, and directed feedback vertex set. The method has also been refined with techniques such as branching and kernelization, leading to improved parameterized algorithms.
Iterative compression has been used to obtain FPT algorithms for a wide range of problems. For example, in the feedback vertex set problem, the technique helps reduce the problem to a simpler case where the graph is a forest after removing the solution. In cluster vertex deletion, it is used to find a set of vertices whose removal makes the graph a disjoint union of cliques. The technique has also been extended to directed graphs, where it is more challenging due to the lack of symmetry.
One lesser-known aspect is that iterative compression can be combined with other techniques, such as randomized branching and color-coding, to solve problems that are not directly amenable to the basic approach. Another is that the technique has been used to derive kernelization results, where the instance is reduced to a smaller equivalent instance. Additionally, the method has been applied to problems in computational biology, such as finding maximum parsimony phylogenetic trees, and to graph modification problems like edge deletion to make a graph planar.3
This article focuses on the algorithmic technique used in parameterized complexity.
Help improve the encyclopedia. Reports go straight to the site manager.