de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

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 (Eds.), 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.