The technique was invented by Reed, Smith and Vetta[1] to show that the problem of odd cycle transversal was solvable in time O(3k 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.
[5] 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 has the following properties: 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: This algorithm calls the compression subroutine a linear number of times.
In their 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.
One way to do this is to test all 2k + 1 choices of which subset of Y is to be removed from the cover and reintroduced back into the graph.