LAUSR

AbstractIn the Subset Feedback Vertex Set (Subset-FVS) problem the input is a graph G on n vertices, a subset T of vertices of G called the “terminal” vertices, and an integer k. The task is to determine whether there exists a subset of vertices of cardinality at most k which together intersect all cycles which pass through the terminals. Subset-FVS generalizes several well studied problems including Feedback Vertex Set and Multiway Cut. This problem is known to be NP-Complete, even in split graphs. Cygan et al. (SIAM J Discrete Math 27(1):290–309, 2013) proved that Subset-FVS is fixed parameter tractable ($$\mathsf {FPT}$$FPT) in general graphs when parameterized by k. In split graphs a simple observation reduces the problem to an equivalent instance of the 3-Hitting Set problem with the same solution size. This directly implies, for Subset-FVSrestricted to split graphs, (i) an $$\mathsf {FPT}$$FPT algorithm which solves the problem in $$\mathcal {O}^{\star } (2.076^k)$$O⋆(2.076k) time (The $$\mathcal {O}^{\star } ()$$O⋆() notation hides polynomial factors.) (Wahlström in Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. Thesis, Department of Computer and Information Science, Linköpings universitet, 2007), and (ii) a kernel of size $$\mathcal {O}(k^3)$$O(k3). We improve both these results for Subset-FVS on split graphs; we derive (i) a kernel of size $$\mathcal {O}(k^2)$$O(k2) which is the best possible unless $$\textsf {NP}\subseteq {\mathsf {coNP}}/{\textsf {poly}}$$NP⊆coNP/poly, and (ii) an algorithm which solves the problem in time $$\mathcal {O}^*(2^k)$$O∗(2k). Our algorithm, in fact, solves Subset-FVS on the more general class of chordal graphs, also in $$\mathcal {O}^*(2^k)$$O∗(2k) time. To the best of our knowledge, the fastest known exact algorithm for Subset-FVS on chordal graphs is based on the 3-Hitting Set algorithm of Fomin et al. (JACM 66(2):8, 2019) which runs in $$\mathcal {O}^*(1.5182^n)$$O∗(1.5182n) time. Applying the results of Fomin et al. (2019) to our $$\mathsf {FPT}$$FPT algorithm yields two exact exponential-time algorithms for Subset-FVS on chordal graphs: a randomized algorithm which runs in $$\mathcal {O}^*(1.5^{n})$$O∗(1.5n) time, and a deterministic algorithm which runs in $$\mathcal {O}^*((1.5+\varepsilon )^{n})$$O∗((1.5+ε)n) time for any fixed $$\varepsilon >0$$ε>0.