On the Complexity of Singly Connected Vertex Deletion

A digraph D is singly connected if for all ordered pairs of vertices [Formula: see text], there is at most one path in D from u to v. In this paper, we study the Singly Connected Vertex Deletion (SCVD) problem: Given an n-vertex digraph D and a positive integer k, does there exist a set [Formula: see text] such that [Formula: see text] and [Formula: see text] is singly connected? This problem may be seen as a directed counterpart of the (Undirected) Feedback Vertex Set problem, as an undirected graph is singly connected if and only if it is acyclic. SCVD is known to be NP-hard on general digraphs. We study the complexity of SCVD on various classes of digraphs such as tournaments, and various generalisations of tournaments such as digraphs of bounded independence number, in- and out-tournaments and local tournaments. We show that unlike the Feedback Vertex Set on Tournaments (FVST) problem, SCVD is polynomial time solvable on tournaments. In addition, we show that SCVD is polynomial time solvable on digraphs of bounded independence number, and on the class of acyclic local tournaments. We also study the parameterized complexity of SCVD, with k as the parameter, on the class of in-tournaments. And we show that on in-tournaments (and out-tournaments), SCVD admits a fixed-parameter tractable algorithm and a quadratic kernel. We also show that on the class of local tournaments, which is a sub-class of in-tournaments, SCVD admits a linear kernel.