A. Clementi and L. Trevisan.
Improved Non-approximability Results for Vertex Cover Problems with
In Proceedings of the 2nd Conference on
Combinatorics and Computing (COCOON'96),
Springer-Verlag, pages 333-342, 1996.
We provide new non-approximability results for the restrictions of the
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.
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.