期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
