Improved non-approximability results for minimum vertex cover with densityconstraints

We provide new non-approximability results for the restrictions of the MIN VERTEX COVER problem to bounded-degree, sparse and dense graphs. We show th at 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 C OVER problem remains APX-complete when restricted to dense graph and thus r ecent techniques developed for several MAX SNP problems restricted to "dens e" instances introduced by Arora et al. (1995) cannot be applied. (C) 1999 Elsevier Science B.V. All rights reserved.