Faster Fixed Parameter Tractable Algorithms for Finding Feedback Vertex Sets

被引：41

作者：

Raman, Venkatesh ^{[1
]}

Saurabh, Saket ^{[1
]}

Subramanian, C. R. ^{[1
]}

机构：

[1] Inst Math Sci, Theoret Comp Sci, CIT Campus, Chennai 600113, Tamil Nadu, India

来源：

ACM TRANSACTIONS ON ALGORITHMS | 2006年 / 2卷 / 03期

关键词：

Feedback vertex set; girth; parameterized complexity;

D O I：

10.1145/1159892.1159898

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A feedback vertex set (fvs) of a graph is a set of vertices whose removal results in an acyclic graph. We show that if an undirected graph on n vertices with minimum degree at least 3 has a fvs on at most 1/3n(1-epsilon) vertices, then there is a cycle of length at most 6/epsilon (for epsilon >= 1/2, we can even improve this to just 6). Using this, we obtain a O (( 12 logk/log log + 6)(k) n(omega)) algorithm for testing whether an undirected graph on n vertices has a fvs of size at most k. Here n(omega) is the complexity of the best matrix multiplication algorithm. The previous best parameterized algorithm for this problem took O ((2k + 1)(k) n(2)) time. We also investigate the fixed parameter complexity of weighted feedback vertex set problem in weighted undirected graphs.

引用

页码：403 / 415

页数：13