University of Sussex
Browse

File(s) not publicly available

On approximability of the independent set problem for low degree graphs

presentation
posted on 2023-06-07, 19:51 authored by Miroslav ChlebikMiroslav Chlebik, Janka Chlebíková
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 - root13/2. Improvements of an approximation ratio below for this case trans late to improvements below B+3/5 of approximation factors for B-MAXIS for all odd B. Consequently, for any odd B greater than or equal to 3, polynomial time algorithms for B-MAXIS exist with approximation ratios arbitrarily close to B+3/5 - 4(5root13-18)/5 (B-2)!!/(B-2)!!. This is currently the best upper bound for B-MAXIS for any odd B, 3 less than or equal to B < 613.

History

Publication status

  • Published

ISSN

0302-9743

Publisher

Springer Berlin / Heidelberg

Volume

3104

Pages

10.0

Presentation Type

  • paper

Event name

11th International Colloquium on Structural Information and Communication Complexity

Event location

Smolenice, SLOVAKIA

Event type

conference

ISBN

978-3-540-22230-9

Department affiliated with

  • Mathematics Publications

Notes

STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY, PROCEEDING

Full text available

  • No

Peer reviewed?

  • Yes

Editors

O Sykora, R Kralovic

Legacy Posted Date

2012-02-06

Usage metrics

    University of Sussex (Publications)

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC