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.