Improved non-approximability results for minimum vertex cover with density constraints
Improved non-approximability results for minimum vertex cover with density constraints
复制标题
DOI：
10.1016/s0304-3975(97)00226-0
复制
发表时间：
1999-08-28
影响因子：
1.1
通讯作者：
Trevisan, L
中科院分区：
文献类型：
--
作者：
Clementi, AEF;Trevisan, L
对于最小顶点覆盖问题对有界度、稀疏和稠密图的限制，我们给出了新的不可逼近结果。我们证明了对于足够大的图B，Hastad(1997)最近证明的1.16下界在没有损失的情况下扩展到有界度B图。然后，我们考虑了不含稠密分支的稀疏图(即处处稀疏图)，我们得到了类似的结果，但在不可逼近性和稀疏性之间有了更好的权衡。最后，我们观察到当限制在稠密图上时，最小顶点覆盖问题仍然是APX-完全的，因此最近Arora等人提出的几个限制于“稠密”实例的Max SNP问题的方法。(1995)不能适用。(C)1999 Elsevier Science B.V.保留所有权利。
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.