Iterative compression and exact algorithms

Iterative compression has recently led to a number of breakthroughs in parameterized complexity. Here, we show that the technique can also be useful in the design of exact exponential time algorithms to solve NP-hard problems. We exemplify our findings with algorithms for the Maximum Independent Set problem, a parameterized and a counting version of d -Hitting Set and the Maximum Induced Cluster Subgraph problem.

Authors

• Fedor V. Fomin
• Serge Gaspers
• Dieter Kratsch
• Mathieu Liedloff Université d'Orlèans
• Saket Saurabh

Keywords

• Exponential time algorithms
• Graph algorithms
• Independent set
• Hitting set
• Induced cluster
• Fixed parameter algorithms
• Iterative compression