Component order connectivity in directed graphs

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

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

40 Downloads (Pure)

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 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)).

OriginalsprogEngelsk
TidsskriftAlgorithmica
Vol/bind84
Udgave nummer9
Sider (fra-til)2767-2784
ISSN0178-4617
DOI
StatusUdgivet - sep. 2022

Bibliografisk note

Funding Information:
Research of JBJ supported by the Independent Research Fund Denmark under grant number DFF 7014-00037B and research of GG supported by the Leverhulme Trust under grant number RPG-2018-161.

Publisher Copyright:
© 2022, The Author(s).

Fingeraftryk

Dyk ned i forskningsemnerne om 'Component order connectivity in directed graphs'. Sammen danner de et unikt fingeraftryk.

Citationsformater