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 ⊆ V, and an integer k as the input. The goal is to determine whether there exists a subset S ⊆ 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 2 k + o ( k ) n O ( 1 ) time, improving the bound obtained from 3-Hitting Set.

Authors

• Tian Bai
• Mingyu Xiao

Keywords

• Subset feedback vertex set
• Tournaments
• Parameterized algorithms
• Iterative compression