Search Results

The Subset Feedback Vertex Set problem (SFVS) is to delete k vertices from a given graph such that in the remaining graph, any vertex in a subset T of vertices (called a terminal set) is not in a cycle. The famous Feedback Vertex Set problem is the special case of SFVS with T being the whole set of vertices. In this paper, we study exact algorithms for SFVS in Split Graphs (SFVS-S) and SFVS in Chordal Graphs (SFVS-C). SFVS-S generalizes the minimum vertex cover problem and the prize-collecting version of the maximum independent set problem in hypergraphs (PCMIS), and SFVS-C further generalizes SFVS-S. Both SFVS-S and SFVS-C are implicit 3-Hitting Set problems. However, it is not easy to solve them faster than 3-Hitting Set. In 2019, Philip, Rajan, Saurabh, and Tale (Algorithmica 2019) proved that SFVS-C can be solved in 𝒪^*(2^k) time, slightly improving the best result 𝒪^*(2.0755^k) for 3-Hitting Set. In this paper, we break the "2^k-barrier" for SFVS-S and SFVS-C by introducing an 𝒪^*(1.8192^k)-time algorithm. This achievement also indicates that PCMIS can be solved in 𝒪^*(1.8192ⁿ) time, marking the first exact algorithm for PCMIS that outperforms the trivial 𝒪^*(2ⁿ) threshold. Our algorithm uses reduction and branching rules based on the Dulmage-Mendelsohn decomposition and a divide-and-conquer method.