## Abstrakt

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}(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 |
---|---|

Titel | 15th International Symposium on Parameterized and Exact Computation, IPEC 2020 |

Redaktører | Yixin Cao, Marcin Pilipczuk |

Antal sider | 16 |

Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |

Publikationsdato | dec. 2020 |

Artikelnummer | 2 |

ISBN (Elektronisk) | 9783959771726 |

DOI | |

Status | Udgivet - dec. 2020 |

Begivenhed | 15th International Symposium on Parameterized and Exact Computation, IPEC 2020 - Virtual, Hong Kong, Kina Varighed: 14. dec. 2020 → 18. dec. 2020 |

### Konference

Konference | 15th International Symposium on Parameterized and Exact Computation, IPEC 2020 |
---|---|

Land/Område | Kina |

By | Virtual, Hong Kong |

Periode | 14/12/2020 → 18/12/2020 |

Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|

Vol/bind | 180 |

ISSN | 1868-8969 |

### Bibliografisk note

Funding Information:Funding Jørgen Bang-Jensen: Research supported by the Independent Research Fund Denmark under grant number DFF 7014-00037B. Gregory Gutin: Research supported by the Leverhulme Trust under grant number RPG-2018-161.

Publisher Copyright:

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