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
more >>>

Computing kernels for the hitting set problem (the problem of
finding a size-k set that intersects each hyperedge of a
hypergraph) is a well-studied computational problem. For hypergraphs
with m hyperedges, each of size at most~d, the best algorithms
can compute kernels of size O(k^d) in ... more >>>