A. Clementi and L. Trevisan.
Improved Non-approximability Results for Vertex Cover Problems with Density Constraints.
In Proceedings of the 2nd Conference on Combinatorics and Computing (COCOON'96),
LNCS 1090, Springer-Verlag, pages 333-342, 1996.
Abstract
We provide new non-approximability results for the restrictions of the Vertex Cover problem to bounded-degree, sparse and dense graphs. We show that for a sufficiently large B, the recent 16/15 lower bound proved by Bellare et al. (FOCS95) extends with negligible loss to graphs with bounded degree B. Then, we consider sparse graphs with no dense components (i.e. everywhere sparse graphs), and we show a similar result but with a better trade-off between non-approximability and sparsity. Finally, we observe that the Vertex Cover problem does not admit an approximation scheme when restricted to dense graphs.