# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### FPT Algorithms for Connected Feedback Vertex Set

##### MPS-Authors

There are no MPG-Authors available

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Misra, N., Philip, G., Raman, V., Saurabh, S., & Sikdar, S. (2010). FPT Algorithms
for Connected Feedback Vertex Set. In M. S. Rahman, & S. Fujita (*WALCOM:
Algorithms and Computation* (pp. 269-280). Berlin: Springer. doi:10.1007/978-3-642-11440-3_25.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0019-DC05-8

##### Abstract

We study the recently introduced \textscConnected Feedback
Vertex Set (CFVS)} problem from the view-point of parameterized algorithms.
CFVS is the connected variant of the classical
\textsc{Feedback Vertex Set} problem and is defined as follows:
given a graph G=(V,E) and an integer k, decide
whether there exists F\subseteq V, |F| ≤q k,
such that G[V \setminus F] is a forest
and G[F] is connected. We show that \textsc{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 a subroutine, a parameterized algorithm for \textsc{Group Steiner
Tree}, a well studied variant of \textsc{Steiner Tree}. We find the
algorithm for \textsc{Group Steiner Tree of independent interest
and believe that it could be useful for obtaining parameterized algorithms
for other connectivity problems.