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.

Postscript, PDF

Errata

(4 April 2019) The analysis of the algorithm Simplicial is faulty and cannot be easily fixed. Thus, we retract the claim of Section 4 that this algorithm achieves a 9/7-approximation. The results of the other sections are not affected.