2004 | OriginalPaper | Chapter
On Approximability of the Independent Set Problem for Low Degree Graphs
Authors : Miroslav Chlebík, Janka Chlebíková
Published in: Structural Information and Communication Complexity
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We obtain slightly improved upper bounds on efficient approximability of the Maximum Independent Set problem in graphs of maximum degree at most B (shortly, B-MaxIS), for small B≥ 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-\frac{\sqrt{13}}{2}$. Improvements of an approximation ratio below $\frac65$ for this case translate to improvements below $\frac{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 $\frac{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.