An 8-approximation algorithm for the subset feedback vertex set problem
An 8-approximation algorithm for the subset feedback vertex set problem
复制标题
DOI：
10.1109/sfcs.1996.548490
复制
发表时间：
1996-10
期刊：
影响因子：
--
通讯作者：
G. Even;J. Naor;L. Zosin
中科院分区：
文献类型：
--
作者：
G. Even;J. Naor;L. Zosin
给出了求最小权子集反馈顶点集问题的8-近似算法。这个问题的输入由一个顶点权重为w(V)的无向图G=(V，E)和一个称为特殊顶点的顶点子集S组成。如果一个圈至少包含一个特殊顶点，则称它为有趣的。一个顶点的子集称为关于S的反馈顶点集，如果它与每个感兴趣的圈相交，则目标是找到一个最小权子集的反馈顶点集。一般情况下的最佳穿透算法只提供了一个对数逼近因子。最小权子集反馈顶点集问题推广了两个NP-完全问题：无向图中的最小权反馈顶点集问题和最小权多向顶点割问题。我们在算法及其分析中使用的主要工具是一种新的多商品流，我们称之为松弛多商品流。宽松的多商品流动是多商品流动和多终端流动的混合体。
We present an 8-approximation algorithm for the problem of finding a minimum weight subset feedback vertex set. The input in this problem consists of an undirected graph G=(V,E) with vertex weights w(v) and a subset of vertices S called special vertices. A cycle is called interesting if it contains at least one special vertex. A subset of vertices is called a subset feedback vertex set with respect to S if it intersects every interesting cycle The goal is to find a minimum weight subset feedback vertex set. The best pervious algorithm for the general case provided only a logarithmic approximation factor. The minimum weight subset feedback vertex set problem generalizes two NP-Complete problems: the minimum weight feedback vertex set problem in undirected graphs and the minimum weight multiway vertex cut problem. The main tool that we use in our algorithm and its analysis is a new version of multi-commodity flow which we call relaxed multi-commodity flow. Relaxed multi-commodity flow is a hybrid of multi-commodity flow and multi-terminal flow.