We study small degree graph problems such as Maximum Independent Set
and Minimum Node Cover and improve approximation lower bounds for
them and for a number of related problems, like Max-B-Set Packing,
Min-B-Set Cover, Max-Matching in B-uniform 2-regular hypergraphs.
For example, we prove NP-hardness factor of 95/94
for Max-3-Dimensional Matching, and factor of 48/47 for
Max-4-Dimensional Matching; in both cases the hardness
result applies even to instances with exactly two occurrences of
each element.