Iterative Compression

Iterative compression is a simple strategy for problems where at most k vertices must be deleted to give a graph some nice structure. Add the vertices one at a time while maintaining a solution. Each new vertex may push the solution up to size k+1, and the job is to compress it back down to k (or to report that no solution of size k exists). An oversized solution gives a lot of structure to work with: you can guess how a smaller solution meets it and solve a more constrained problem. I develop the method and apply it to Feedback Vertex Set.