Satellites and Mirrors for Solving Independent Set on Sparse Graphs
Joachim Kneis, Alexander Langer · RWTH Publications (RWTH Aachen) · 2009
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.