AIB 2009-08: Satellites and Mirrors for Solving Independent Set on Sparse Graphs

The following technical report is available from http://aib.informatik.rwth-aachen.de:

Satellites and Mirrors for Solving Independent Set on Sparse Graphs Joachim Kneis, Alexander Langer AIB 2009-08

We study the well-known Maximum Independent Set (MIS) problem and introduce the notion of satellites of a node. Branching on nodes with satellites is extremely simple. Nevertheless, satellites can be used to overcome a couple of hard cases in previous algorithms. Together with the notion of mirrors, introduced by Fomin, Grandoni, and Kratsch, they can be used to solve MIS in time bounded by O^*(1.1928^{m-n}), which is O^*(1.0922^n) for cubic graphs. This improves over previous results for sparse graphs.