Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR96-016 | 6th February 1996 00:00

Improved Non-approximability Results for Minimum Vertex Cover with Density Constraints



We provide new non-approximability results for the restrictions
of the min-VC 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. 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-VC problem remains
APX-complete when restricted to dense graph and thus
recent techniques developed for several MAXSNP problems
restricted to ``dense'' instances introduced by Arora et al.
cannot be applied.

ISSN 1433-8092 | Imprint