Faster fixed parameter tractable algorithms for finding feedback vertex sets

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/3 n 1 − ϵ vertices, then there is a cycle of length at most 6/ϵ (for ϵ ≥ 1/2, we can even i...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on algorithms 2006-07, Vol.2 (3), p.403-415
Main Authors: Raman, Venkatesh, Saurabh, Saket, Subramanian, C. R.
Format: Article
Language:English
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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/3 n 1 − ϵ vertices, then there is a cycle of length at most 6/ϵ (for ϵ ≥ 1/2, we can even improve this to just 6).Using this, we obtain a O ((12 log k /log log k + 6) k n ω algorithm for testing whether an undirected graph on n vertices has a fvs of size at most k . Here n ω is the complexity of the best matrix multiplication algorithm. The previous best parameterized algorithm for this problem took O ((2 k + 1) k n 2 ) time.We also investigate the fixed parameter complexity of weighted feedback vertex set problem in weighted undirected graphs.
ISSN:1549-6325
1549-6333
DOI:10.1145/1159892.1159898