On Approximability of the Independent Set Problem for Low Degree Graphs

Miroslav Chlebik, Janka Chlebikova

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We obtain slightly improved upper bounds on efficient approximability of the MAXIMUM INDEPENDENT SET problem in graphs of maximum degree at most Β (shortly, Β-\MaxIS), for small Β≥ 3. The degree-three case plays a role of the central problem, as many of the results for the other problems
use reductions to it. Our careful analysis of approximation algorithms of Berman and Fujito for 3-MaxIS shows that one can achieve approximation ratio arbitrarily close to 3-√{13}/2. Improvements of an approximation ratio below 6/5 for this case translate to improvements below (B+3)/5 of approximation factors for B-MaxIS for all odd B. Consequently, for any odd B≥3, polynomial time algorithms for B-MaxIS exist with approximation ratios arbitrarily close to
(B+3)/5-\frac{4(5\sqrt{13}-18)}5\frac{(B-2)!!}{(B+1)!!}. This is currently the best upper bound for B-MaxIS for any odd B, 3≥ B<613.
Original languageEnglish
Title of host publicationStructural information and communication complexity
Subtitle of host publication11th international colloquium, SIROCCO 2004, Smolenice Castle, Slowakia, June 21-23, 2004. proceedings
EditorsRatislav Kralovic, Ondrej Sykora
ISBN (Electronic)9783540277965
ISBN (Print)9783540222309
Publication statusPublished - 2004

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


  • maximum independent set
  • approximation algorithm
  • bounded degree graphs


Dive into the research topics of 'On Approximability of the Independent Set Problem for Low Degree Graphs'. Together they form a unique fingerprint.

Cite this