Abstract
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 DX 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^(16(n?))) for the parameter n?. We complement the latter by showing that there is no algorithm of time complexity O^*(2^o(n?)) 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^*(2^O(k? log (k?))) to O^*(2^O(klog (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(klog ?)) unless ETH fails and it is a longstanding problem to decide whether Directed Feedback Vertex Set admits an algorithm of time complexity O^*(2^o(klog k)).
BibTeX  Entry
@InProceedings{bangjensen_et_al:LIPIcs:2020:13305,
author = {J{\o}rgen BangJensen and Eduard Eiben and Gregory Gutin and Magnus Wahlstr{\"o}m and Anders Yeo},
title = {{Component Order Connectivity in Directed Graphs}},
booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)},
pages = {2:12:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771726},
ISSN = {18688969},
year = {2020},
volume = {180},
editor = {Yixin Cao and Marcin Pilipczuk},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13305},
URN = {urn:nbn:de:0030drops133058},
doi = {10.4230/LIPIcs.IPEC.2020.2},
annote = {Keywords: Parameterized Algorithms, component order connectivity, directed graphs, semicomplete digraphs}
}
Keywords: 

Parameterized Algorithms, component order connectivity, directed graphs, semicomplete digraphs 
Collection: 

15th International Symposium on Parameterized and Exact Computation (IPEC 2020) 
Issue Date: 

2020 
Date of publication: 

04.12.2020 