FPT algorithms for connected feedback vertex set

DOI10.1007/978-3-642-11440-3_25MaRDI QIDQ3404454zbMATH OpenOpenAlexFDO

Authors Neeldhara Misra, Geevarghese Philip, Venkatesh Raman, Saket Saurabh, Somnath Sikdar

Publication date 9 February 2010

Published in WALCOM: Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.3180

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Nonnumerical algorithms (68W05)

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 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(sqrtklogk)}{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.

Recommendations

• FPT algorithms for connected feedback vertex set
• Parameterized and Exact Computation
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Computing and Combinatorics
• On parameterized independent feedback vertex set

Cited in

(11)

• FPT algorithms for connected feedback vertex set
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• Connecting face hitting sets in planar graphs
• Vertex Exponential Algorithms for Connected f-Factors
• Lossy kernels for connected dominating set on sparse graphs
• Conflict free feedback vertex set: a parameterized dichotomy
• Connected feedback vertex set on AT-free graphs
• Lossy kernels for connected dominating set on sparse graphs
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• FPT algorithms for domination in sparse graphs and beyond
• Algorithmic properties of sparse digraphs

This page was built for publication: FPT algorithms for connected feedback vertex set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3404454)