## Greedy Approximations of Independent Sets in Low Degree Graphs

Magnús M. Halldórsson

Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.
Kiyohito Yoshihara

Department of Computer Science, Tokyo Institute of Technology

We investigate the power of a family of greedy algorithms for the
independent set problem in cubic graphs and graphs of maximum degree
three. These algorithm iteratively select vertices of minimum degree,
but differ in the secondary rule for choosing among many candidates.
We study three such algorithms, and prove tight performance ratios,
with the best one being 9/7 \approx 1.28. All of these algorithms
are practical and run in linear time, in contrast with the algorithm
with the best performance ratio known of 1.2.
We also show certain inherent limitations in the power of this family
of algorithm: any algorithm that greedily selects vertices of minimum
has a performance ratio at least 1.25 on degree-three graphs, even if
given an oracle to choose among candidate vertices of minimum degree.