On approximation properties of the independent set problem for low degree graphs

Citation
P. Berman et T. Fujito, On approximation properties of the independent set problem for low degree graphs, THEOR C SYS, 32(2), 1999, pp. 115-132
Citations number
16
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORY OF COMPUTING SYSTEMS
ISSN journal
14324350 → ACNP
Volume
32
Issue
2
Year of publication
1999
Pages
115 - 132
Database
ISI
SICI code
1432-4350(199903/04)32:2<115:OAPOTI>2.0.ZU;2-9
Abstract
The subject of this paper is the Independent Set problem for bounded node d egree graphs. It is shown that the problem remains MAX SNP-complete even wh en graphs are restricted to being of degree bounded by 3 or to being 3-regu lar. Some related problems are also shown to be MAX SNP-complete at the low est possible degree bounds. We next study a better polynomial time approxim ation of the problem for degree 3 graphs. The performance ratio is improved from the previous best of 5/4 to arbitrarily close to 6/5 for degree 3 gra phs and to 7/6 for cubic graphs. When combined with existing techniques thi s result also leads to approximation ratios, (B + 3)/5 + epsilon for the in dependent set problem and 2 - 5/(B + 3) + epsilon for the vertex cover prob lem on graphs of degree B, improving previous bounds for relatively small o dd B.