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.$ viol{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 $ell$, 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 $ell$ vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for $ell=1.$ We study parametered complexity of DCOC for general and semicomplete digraphs with the following parameters: $k, ell,ell+k$ and $n-ell$. 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. gutin{The upper bound $O^*(2^{16k})$ implies the upper bound $O^*(2^{16(n-ell)})$ for the parameter $n-ell.$ We complement the latter by showing that there is no algorithm of time complexity $O^*(2^{o({n-ell})})$ unless ETH fails.} Finally, we improve viol{(in dependency on $ell$)} the upper bound of G{{o}}ke, Marx and Mnich (2019) for the time complexity of DCOC with parameter $ell+k$ on general digraphs from $O^*(2^{O(kelllog (kell))})$ to $O^*(2^{O(klog (kell))}).$ 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(klog ell)})$ 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(klog k)}).$