Exact algorithms for restricted subset feedback vertex set in chordal and split graphs.

The Restricted Subset Feedback Vertex Set problem (R-SFVS) takes a graph G = (V , E) , a terminal set T ⊆ V , and an integer k as the input. The task is to determine whether there exists a subset S ⊆ V ∖ T of at most k vertices, after deleting which no terminal in T is contained in a cycle in the remaining graph. R-SFVS is NP -complete even when the input graph is restricted to split graphs. In this paper, we mainly show that R-SFVS in chordal and split graphs can be solved in O (1.1550 | V |) time and exponential space or in O (1.1605 | V |) time and polynomial space, significantly improving all previous results. As a by-product, we show that the Maximum Independent Set problem parameterized by the edge clique cover number is fixed-parameter tractable. Furthermore, by using a simple reduction from R-SFVS to Vertex Cover , we obtain an O ⁎ (1.2738 k) -time parameterized algorithm and a tight O (k 2) -kernel for R-SFVS in chordal and split graphs. [ABSTRACT FROM AUTHOR]