Bi-Weekly Talk: Komal Muluk: On the complexity of singly connected vertex deletion

Wednesday, May 05, 2021, 10:30am

Location: Online session

Speaker: Komal Muluk

 

Abstract: 

A digraph D is singly connected if for all ordered pairs of vertices u,v in V(D), there is at most one path in D from u to v. We study the singly connected vertex deletion (SCVD) problem in which given a digraph and a positive integer k, the task is to verify whether there exist a set S of vertices of size at most k such that the deletion of S renders a singly connected graph. SCVD is known to be NP-hard on general digraphs. 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. We show that unlike the problem feedback vertex set on tournaments (FVST), 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. And we show that on in-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.