FPT algorithms for connected feedback vertex set

DOI10.1007/978-3-642-11440-3_25zbMATH Open1274.68674arXiv0909.3180OpenAlexW2163789465MaRDI QIDQ3404454FDOQ3404454

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)

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.

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

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

Mathematics Subject Classification ID

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

Cited In (10)

• Title not available (Why is that?)
• Connecting face hitting sets in planar graphs
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• Title not available (Why is that?)
• FPT algorithms for connected feedback vertex set
• Kernelization Hardness of Connectivity Problems in d-Degenerate Graphs
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• FPT algorithms for domination in sparse graphs and beyond
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• Vertex Exponential Algorithms for Connected f-Factors

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)