Component order connectivity in directed graphs

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

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

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(216k) but not in time O(2o(k)) unless the Exponential Time Hypothesis (ETH) fails. The upper bound O(216k) implies the upper bound O(216(n−`)) for the parameter n− `. We complement the latter by showing that there is no algorithm of time complexity O(2o(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(2O(k` log(k`))) to O(2O(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(2o(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(2o(k log k)).

OriginalsprogEngelsk
Titel15th International Symposium on Parameterized and Exact Computation, IPEC 2020
RedaktørerYixin Cao, Marcin Pilipczuk
Antal sider16
ForlagSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publikationsdatodec. 2020
Artikelnummer2
ISBN (Elektronisk)9783959771726
DOI
StatusUdgivet - dec. 2020
Begivenhed15th International Symposium on Parameterized and Exact Computation, IPEC 2020 - Virtual, Hong Kong, Kina
Varighed: 14. dec. 202018. dec. 2020

Konference

Konference15th International Symposium on Parameterized and Exact Computation, IPEC 2020
Land/OmrådeKina
ByVirtual, Hong Kong
Periode14/12/202018/12/2020
NavnLeibniz International Proceedings in Informatics, LIPIcs
Vol/bind180
ISSN1868-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;

Fingeraftryk

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

Citationsformater