On Approximability 	of the Independent Set Problem for Low Degree Graphs

Miroslav Chlebik; Janka Chlebikova

doi:10.1007/978-3-540-27796-5_5

On Approximability of the Independent Set Problem for Low Degree Graphs

Miroslav Chlebik
, Janka Chlebikova

University of Sussex

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

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	https://doi.org/10.1007/978-3-540-27796-5_5
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

Access to Document

10.1007/978-3-540-27796-5_5

Cite this

Chlebik, M., & Chlebikova, J. (2004). On Approximability of the Independent Set Problem for Low Degree Graphs. In R. Kralovic, & O. Sykora (Eds.), Structural information and communication complexity : 11th international colloquium, SIROCCO 2004, Smolenice Castle, Slowakia, June 21-23, 2004. proceedings (pp. 47-56). (Lecture Notes in Computer Science; Vol. 3104). Springer. https://doi.org/10.1007/978-3-540-27796-5_5

Chlebik, Miroslav ; Chlebikova, Janka. / On Approximability of the Independent Set Problem for Low Degree Graphs. Structural information and communication complexity : 11th international colloquium, SIROCCO 2004, Smolenice Castle, Slowakia, June 21-23, 2004. proceedings. editor / Ratislav Kralovic ; Ondrej Sykora . Springer, 2004. pp. 47-56 (Lecture Notes in Computer Science).

@inproceedings{cbe55ddd2e124610a040141314d8238a,

title = "On Approximability of the Independent Set Problem for Low Degree Graphs",

abstract = "We obtain slightly improved upper bounds on efficient approximability of the MAXIMUM INDEPENDENT SET problem in graphs of maximum degree at most Β (shortly, Β-\textbackslash{}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-\textbackslash{}frac\{4(5\textbackslash{}sqrt\{13\}-18)\}5\textbackslash{}frac\{(B-2)!!\}\{(B+1)!!\}. This is currently the best upper bound for B-MaxIS for any odd B, 3≥ B<613.",

keywords = " maximum independent set, approximation algorithm, bounded degree graphs",

author = "Miroslav Chlebik and Janka Chlebikova",

year = "2004",

doi = "10.1007/978-3-540-27796-5\_5",

language = "English",

isbn = "9783540222309",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "47--56",

editor = "Kralovic, \{Ratislav \} and \{Sykora \}, \{Ondrej \}",

booktitle = "Structural information and communication complexity",

address = "Netherlands",

}

Chlebik, M & Chlebikova, J 2004, On Approximability of the Independent Set Problem for Low Degree Graphs. in R Kralovic & O Sykora (eds), Structural information and communication complexity : 11th international colloquium, SIROCCO 2004, Smolenice Castle, Slowakia, June 21-23, 2004. proceedings. Lecture Notes in Computer Science, vol. 3104, Springer, pp. 47-56. https://doi.org/10.1007/978-3-540-27796-5_5

On Approximability of the Independent Set Problem for Low Degree Graphs. / Chlebik, Miroslav; Chlebikova, Janka.
Structural information and communication complexity : 11th international colloquium, SIROCCO 2004, Smolenice Castle, Slowakia, June 21-23, 2004. proceedings. ed. / Ratislav Kralovic; Ondrej Sykora . Springer, 2004. p. 47-56 (Lecture Notes in Computer Science; Vol. 3104).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - On Approximability of the Independent Set Problem for Low Degree Graphs

AU - Chlebik, Miroslav

AU - Chlebikova, Janka

PY - 2004

Y1 - 2004

N2 - 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.

AB - 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.

KW - maximum independent set

KW - approximation algorithm

KW - bounded degree graphs

U2 - 10.1007/978-3-540-27796-5_5

DO - 10.1007/978-3-540-27796-5_5

M3 - Conference contribution

SN - 9783540222309

T3 - Lecture Notes in Computer Science

SP - 47

EP - 56

BT - Structural information and communication complexity

A2 - Kralovic, Ratislav

A2 - Sykora , Ondrej

PB - Springer

ER -

Chlebik M, Chlebikova J. On Approximability of the Independent Set Problem for Low Degree Graphs. In Kralovic R, Sykora O, editors, Structural information and communication complexity : 11th international colloquium, SIROCCO 2004, Smolenice Castle, Slowakia, June 21-23, 2004. proceedings. Springer. 2004. p. 47-56. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-27796-5_5