A parameterized algorithm for subset feedback vertex set in tournaments

The SUBSET FEEDBACK VERTEX SET problem (SFVS) takes an n-vertex graph G = (V, E), a terminal set T subset of V, and an integer k as the input. The goal is to determine whether there exists a subset S subset of V of at most k vertices whose removal makes no terminal in T contained in a cycle in the remaining graph. When T = V, SFVS degenerates to the classical FEEDBACK VERTEX SET problem (FVS). Both SFVS and FVS have been extensively studied in parameterized algorithms. In this paper, we study parameterized algorithms for SUBSET FEEDBACK VERTEX SET IN TOURNAMENTS (SFVST), i.e., SFVS with the restriction that the input graph is always a tournament. By using the iterative compression method and a novel dynamic programming, we show that SFVST can be solved in 2k+o(k)nO(1) time, improving the bound obtained from 3-HITTINg SET.(c) 2023 Elsevier B.V. All rights reserved.