Header menu link for other important links
X
On the Complexity of Singly Connected Vertex Deletion
A. Das, , J. Madathil, K. Muluk, N. Purohit, S. Saurabh
Published in Springer
2020
Volume: 12126 LNCS
   
Pages: 237 - 250
Abstract
A digraph D is singly connected if for all ordered pairs of vertices (Formula Presented), 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 Presented) such that (Formula Presented) and D - S 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. © Springer Nature Switzerland AG 2020.
About the journal
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
ISSN03029743