FPT algorithms for Connected Feedback Vertex Set

Neeldhara Misra (), Geevarghese Philip (), Venkatesh Raman (), Saket Saurabh () and Somnath Sikdar ()
Additional contact information
Neeldhara Misra: The Institute of Mathematical Sciences
Geevarghese Philip: The Institute of Mathematical Sciences
Venkatesh Raman: The Institute of Mathematical Sciences
Saket Saurabh: The Institute of Mathematical Sciences
Somnath Sikdar: RWTH Aachen University

Journal of Combinatorial Optimization, 2012, vol. 24, issue 2, No 5, 146 pages

Abstract: Abstract 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 F⊆V, |F|≤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 a 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 could be useful for obtaining parameterized algorithms for other connectivity problems.

Keywords: Parameterized algorithms; FPT algorithms; Connected Feedback Vertex Set; Feedback Vertex Set; Group Steiner Tree; Steiner Tree; Directed Steiner Out-Tree; Hardness of polynomial kernelization; Subexponential FPT algorithms; H-minor-free graphs; Dynamic programming over tree decompositions (search for similar items in EconPapers)
Date: 2012
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-011-9394-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:24:y:2012:i:2:d:10.1007_s10878-011-9394-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-011-9394-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().