|
Abstract : |
Abstract. The main problem we consider in this paper is the Independent Set problem for bounded degree graphs. It is shown that the problem remains MAX SNP--complete when the maximum degree is bounded by 3. Some related problems are also shown to be MAX SNP--complete at the lowest possible degree bounds. Next we study better poly--time approximation of the problem for degree 3 graphs, and improve the previously best ratio, 5 4, to arbitrarily close to 6 5. This result also provides improved poly--time approximation ratios,, |
