Iterative Compression and Exact Algorithms

Abstract Iterative Compression has recently led to a number of breakthroughs in parameterized complexity. The main purpose of this paper is to show that iterative compression can also be used in the design of exact exponential time algorithms. We exemplify our findings with algorithms for the Maximum Independent Set problem, a counting version of k - Hitting Set and the Maximum Induced Cluster Subgraph problem.

Authors

• Fedor V. Fomin
• Serge Gaspers
• Dieter Kratsch
• Mathieu Liedloff
• Saket Saurabh 0001

Keywords

No keywords are indexed for this paper.