A. Clementi and L. Trevisan.<br>
<b>Improved Non-approximability Results for Vertex Cover Problems with 
Density Constraints.</b><br>
In  <i>Proceedings of the <a
href = "http://www.csd.hku.hk/cocoon96.html">2nd Conference on
Combinatorics and Computing (COCOON'96)</a></i>, <br>LNCS 1090, 
Springer-Verlag, pages 333-342, 1996.


<dl>




<dt> <b> Abstract </b> <dd>

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 <i>B</i>, the recent 16/15 lower bound proved by Bellare et
al. (FOCS95) extends with negligible
loss to graphs with bounded degree <i>B</i>.
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.

</dl>