## 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 ^{16}^{k}) but not in time O^{∗}(2 ^{o}^{(}^{k}^{)}) unless the Exponential Time Hypothesis (ETH) fails. The upper bound O^{∗}(2 ^{16}^{k}) 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}^{(}^{k}^{log}^{(}^{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}^{(}^{k}^{log}^{ℓ}^{)}) 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}^{(}^{k}^{log}^{k}^{)}).

Originalsprog | Engelsk |
---|---|

Tidsskrift | Algorithmica |

Vol/bind | 84 |

Udgave nummer | 9 |

Sider (fra-til) | 2767-2784 |

ISSN | 0178-4617 |

DOI | |

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