2022/01/02 by Giacomo Paesani, Paesani, Giacomo, Daniël Paulusma +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Complexity (cs.CC) #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Error Correcting Code Techniques #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2201.00430
openalex publication_date 2022/01/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the Feedback Vertex Set problem, we aim to find a small set S of vertices in a graph intersecting every cycle. The Subset Feedback Vertex Set problem requires S to intersect only those cycles that include a vertex of some specified set T. We also consider the Weighted Subset Feedback Vertex Set problem, where each vertex u has weight w(u)>0 and we ask that S has small weight. By combining known NP-hardness results with new polynomial-time results we prove full complexity dichotomies for Subset Feedback Vertex Set and Weighted Subset Feedback Vertex Set for H-free graphs, that is, graphs that do not contain a graph H as an induced subgraph.