文章基本信息

标题：Component Order Connectivity in Directed Graphs
本地全文：下载
作者：Bang-Jensen, Jørgen ; Eduard Eiben ; Gregory Gutin 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：180
页码：1-16
DOI：10.4230/LIPIcs.IPEC.2020.2
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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)).
关键词：Parameterized Algorithms; component order connectivity; directed graphs; semicomplete digraphs