Department of
Applied
Mathematics

A Simple $O (2^{0.288 n})$ Independent Set Algorithm

Dieter Kratsch

Abstract

We apply ``Measure and Conquer" to analyse a very simple Branch & Reduce algorithm solving the well-studied Maximum Independent Set problem. We obtain a running time of $O(2^{0.288 n})$, which is competitive with the current best time bounds obtained with far more complicated algorithms (and naive analysis). We also provide an $\Omega (2^{0.166 n})$ lower bound on the time complexity of the algorithm.