FPT Algorithms for Connected Feedback Vertex Set

2009/09/17 by Neeldhara Misra, Geevarghese Philip, Misra, Neeldhara +7 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Interconnection Networks and Systems #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.0909.3180

openalex publication_date 2009/09/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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(√(k)log k)}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.

Cited by

• Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set

Related

• An improved FPT algorithm for Independent Feedback Vertex Set
• Improved FPT Algorithms for Deletion to Forest-like Structures
• An Improved Parameterized Algorithm for the Independent Feedback Vertex Set Problem
• Directed Feedback Vertex Set Problem is FPT
• Detecting Feedback Vertex Sets of Size k in O^⋆(2.7^k) Time