## Abstract

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.

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 language | English |
---|---|

Title of host publication | Structural information and communication complexity |

Subtitle of host publication | 11th international colloquium, SIROCCO 2004, Smolenice Castle, Slowakia, June 21-23, 2004. proceedings |

Editors | Ratislav Kralovic, Ondrej Sykora |

Publisher | Springer |

Pages | 47-56 |

ISBN (Electronic) | 9783540277965 |

ISBN (Print) | 9783540222309 |

DOIs | |

Publication status | Published - 2004 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 3104 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

## Keywords

- maximum independent set
- approximation algorithm
- bounded degree graphs