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
Go to the corresponding LIPIcs Volume Portal

Bang-Jensen, Jørgen ; Eiben, Eduard ; Gutin, Gregory ; Wahlström, Magnus ; Yeo, Anders

Component Order Connectivity in Directed Graphs

LIPIcs-IPEC-2020-2.pdf (0.6 MB)


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

  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 =		{},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI