Component order connectivity in directed graphs

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

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

3 Downloads (Pure)


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 strongly connected component in D- X has at most ℓ vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for ℓ= 1. We study the 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(klog(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(klogk)).

Original languageEnglish
Issue number9
Pages (from-to)2767-2784
Publication statusPublished - Sept 2022


  • Directed graph
  • Order connectivity
  • Parameterized Complexity
  • Strong connectivity


Dive into the research topics of 'Component order connectivity in directed graphs'. Together they form a unique fingerprint.

Cite this