Abstract.
The subject of this paper is the Independent Set problem for bounded node degree graphs. It is shown that the problem remains MAX SNP -complete even when graphs are restricted to being of degree bounded by 3 or to being 3-regular. Some related problems are also shown to be MAX SNP -complete at the lowest possible degree bounds. We next study a better polynomial time approximation 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 graphs and to 7/6 for cubic graphs. When combined with existing techniques this result also leads to approximation ratios, (B+3)/5+ε for the independent set problem and 2-5/(B+3)+ε for the vertex cover problem on graphs of degree B , improving previous bounds for relatively small odd B .
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Additional information
Received March 1996, and in final form May 1998.
Rights and permissions
About this article
Cite this article
Berman, P., Fujito, T. On Approximation Properties of the Independent Set Problem for Low Degree Graphs . Theory Comput. Systems 32, 115–132 (1999). https://doi.org/10.1007/s002240000113
Issue Date:
DOI: https://doi.org/10.1007/s002240000113