Satellites and Mirrors for Solving Independent Set on Sparse Graphs
Joachim Kneis, Alexander Langer
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.