Improved non-approximability results for minimum vertex cover with density constraints

We provide new non-approximability results for the restrictions of the MIN VERTEX COVER problem to bounded-degree, sparse and dense graphs. We show that for a sufficiently large B, the recent 1.16 lower bound proved by Hastad (1997) 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 MIN VERTEX COVER problem remains APX-complete when restricted to dense graph and thus recent techniques developed for several MAX SNP problems restricted to "dense" instances introduced by Arora et al. (1995) cannot be applied. (C) 1999 Elsevier Science B.V. All rights reserved.