License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.IPEC.2020.2
URN: urn:nbn:de:0030-drops-133058
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13305/
Bang-Jensen, Jørgen ;
Eiben, Eduard ;
Gutin, Gregory ;
Wahlström, Magnus ;
Yeo, Anders
Component Order Connectivity in Directed Graphs
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 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^(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 long-standing 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 Bang-Jensen 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:1--2:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-172-6},
ISSN = {1868-8969},
year = {2020},
volume = {180},
editor = {Yixin Cao and Marcin Pilipczuk},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13305},
URN = {urn:nbn:de:0030-drops-133058},
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 |
