2019/12/15 by Bin Sheng, Sheng, Bin
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Component (thermodynamics) #Computational Complexity (cs.CC) #Computer science #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Feedback vertex set #Graph #Interconnection Networks and Systems #Kernelization #Mathematics #Parameterized complexity #Physics #Set (abstract data type) #Vertex (graph theory) #cs.CC #cs.DS #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1912.06966
arxiv created 2019/12/15 · openalex publication_date 2019/12/15 · arxiv updated 2019/12/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An r-pseudoforest is a graph in which each component can be made into a forest by deleting at most r edges, and a d-quasi-forest is a graph in which each component can be made into a forest by deleting at most d vertices. In this paper, we study the parameterized tractability of deleting minimum number of vertices to obtain r-pseudoforest and d-quasi-forest, generalizing the well studied feedback vertex set problem. We first provide improved FPT algorithm and kernelization results for the r-pseudoforest deletion problem and then we show that the d-quasi-forest deletion problem is also FPT.