FPT Algorithms for Connected Feedback Vertex Set

Details FPT Algorithms for Connected Feedback Vertex Set FPT Algorithms for Connected Feedback Vertex Set

2009-09-17

arxiv.org/abs/0909.3180v1

Computer Science

Data Structures and Algorithms

12 pages

Scientific paper

We study the recently introduced Connected Feedback Vertex Set (CFVS) problem from the view-point of parameterized algorithms. CFVS is the connected variant of the classical Feedback Vertex Set problem and is defined as follows: given a graph G=(V,E) and an integer k, decide whether there exists a subset F of V, of size at most k, such that G[V F] is a forest and G[F] is connected. We show that Connected Feedback Vertex Set can be solved in time $O(2^{O(k)}n^{O(1)})$ on general graphs and in time $O(2^{O(\sqrt{k}\log k)}n^{O(1)})$ on graphs excluding a fixed graph H as a minor. Our result on general undirected graphs uses as subroutine, a parameterized algorithm for Group Steiner Tree, a well studied variant of Steiner Tree. We find the algorithm for Group Steiner Tree of independent interest and believe that it will be useful for obtaining parameterized algorithms for other connectivity problems.

Affiliated with

Also associated with

No associations

Rating

FPT Algorithms for Connected Feedback Vertex Set does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with FPT Algorithms for Connected Feedback Vertex Set, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and FPT Algorithms for Connected Feedback Vertex Set will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-390711