Component order connectivity in directed graphs

A directed graph D is semicomplete if for every pair x, y of vertices of D, there is at least one arc between x and y. Thus, a tournament is a semicomplete digraph. In the Directed Component Order Connectivity (DCOC) problem, given a digraph D = (V, A) and a pair of natural numbers k and `, we are to decide whether there is a subset X of V of size k such that the largest strong connectivity component in D − X has at most ` vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for ` = 1. We study parameterized complexity of DCOC for general and semicomplete digraphs with the following parameters: k, `, ` + k and n − `. In particular, we prove that DCOC with parameter k on semicomplete digraphs can be solved in time O^∗(2^16k) but not in time O^∗(2^o(k⁾) unless the Exponential Time Hypothesis (ETH) fails. The upper bound O^∗(2^16k) implies the upper bound O^∗(2¹⁶⁽n−`<sup>)</sup>) for the parameter n− `. We complement the latter by showing that there is no algorithm of time complexity O^∗(2^o(n−`<sup>)</sup>) unless ETH fails. Finally, we improve (in dependency on `) the upper bound of Göke, Marx and Mnich (2019) for the time complexity of DCOC with parameter ` + k on general digraphs from O<sup>∗</sup>(2<sup>O</sup>(k` log(k`<sup>))</sup>) to O<sup>∗</sup>(2<sup>O</sup>(k log(k`⁾⁾). Note that Drange, Dregi and van’t Hof (2016) proved that even for the undirected version of DCOC on split graphs there is no algorithm of running time O^∗(2^o(k log `⁾) unless ETH fails and it is a long-standing problem to decide whether Directed Feedback Vertex Set admits an algorithm of time complexity O^∗(2^o(k log k⁾).