A Unified Local Ratio Approximation of Node-Deletion Problems (Extended Abstract)
A Unified Local Ratio Approximation of Node-Deletion Problems (Extended Abstract)
复制标题
节点删除问题的统一局部比率近似（扩展摘要）
DOI：
10.1007/3-540-61680-2_54
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Toshihiro Fujito
中科院分区：
文献类型：
--
作者：
Toshihiro Fujito
在本文中，我们考虑一种针对具有非平凡和遗传图属性的节点删除问题的统一近似方法。 16 年前，通过顶点覆盖问题的一些通用近似保留约简，证明了非平凡遗传属性的每个节点删除问题都是 NP 完全的。当时提出的一个开放性问题涉及近似性的另一个方向：其他节点删除问题是否可以像顶点覆盖一样好地近似？当前论文的目标是沿着上述研究方向迈出第一步。更具体地说，提出了一种通用近似算法，该算法适用于遗传属性的每个节点删除问题。然后将看到，在简单和自然的加权方案下，作为算法的参数，各种节点删除问题可以用比率2来近似，或者用一些不平凡的性能比率来近似。本文考虑了两种类型的图属性：一种具有有限数量的最小禁止图，另一种是满足（子）图的所有边集形成某些拟阵的独立集族。
In this paper we consider a unified approximation method for node-deletion problems with nontrivial and hereditary graph properties. It was proved 16 years ago that every node-deletion problems for a nontrivial hereditary property isNP-complete via a few genericapproximation preservingreductions from the Vertex Cover problem. An open problem posed at that time is concerned with the other direction of approximability: can other node-deletion problems be approximated as good as the Vertex Cover ?The goal of the current paper is to take a first step along the direction of research suggested above. More specifically, one generic approximation algorithm is presented, which is applicable to every node-deletion problem for a hereditary property. It will be seen then that under simple and natural weighting schemes, serving as a parameter of the algorithm, various node-deletion problems can be approximated with ratio 2, or otherwise with some nontrivial performance ratios. Two types of graph properties are considered in this paper: one with a finite number of minimal forbidden graphs, and the other in which all the edge sets of satisfying (sub)graphs form a family of independent sets for some matroid.