License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.11
URN: urn:nbn:de:0030-drops-145925
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14592/
Bang-Jensen, Jørgen ;
Klinkby, Kristine Vitting ;
Saurabh, Saket
k-Distinct Branchings Admits a Polynomial Kernel
Abstract
Unlike the problem of deciding whether a digraph D = (V,A) has ? in-branchings (or ? out-branchings) is polynomial time solvable, the problem of deciding whether a digraph D = (V,A) has an in-branching B^- and an out-branching B^+ which are arc-disjoint is NP-complete. Motivated by this, a natural optimization question that has been studied in the realm of Parameterized Complexity is called Rooted k-Distinct Branchings. In this problem, a digraph D = (V,A) with two prescribed vertices s,t are given as input and the question is whether D has an in-branching rooted at t and an out-branching rooted at s such that they differ on at least k arcs. Bang-Jensen et al. [Algorithmica, 2016 ] showed that the problem is fixed parameter tractable (FPT) on strongly connected digraphs. Gutin et al. [ICALP, 2017; JCSS, 2018 ] completely resolved this problem by designing an algorithm with running time 2^{?(k² log² k)}n^{?(1)}. Here, n denotes the number of vertices of the input digraph. In this paper, answering an open question of Gutin et al., we design a polynomial kernel for Rooted k-Distinct Branchings. In particular, we obtain the following: Given an instance (D,k,s,t) of Rooted k-Distinct Branchings, in polynomial time we obtain an equivalent instance (D',k',s,t) of Rooted k-Distinct Branchings such that |V(D')| ≤ ?(k²) and the treewidth of the underlying undirected graph is at most ?(k). This result immediately yields an FPT algorithm with running time 2^{?(klog k)}+ n^{?(1)}; improving upon the previous running time of Gutin et al. For our algorithms, we prove a structural result about paths avoiding many arcs in a given in-branching or out-branching. This result might turn out to be useful for getting other results for problems concerning in-and out-branchings.
BibTeX - Entry
@InProceedings{bangjensen_et_al:LIPIcs.ESA.2021.11,
author = {Bang-Jensen, J{\o}rgen and Klinkby, Kristine Vitting and Saurabh, Saket},
title = {{k-Distinct Branchings Admits a Polynomial Kernel}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {11:1--11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14592},
URN = {urn:nbn:de:0030-drops-145925},
doi = {10.4230/LIPIcs.ESA.2021.11},
annote = {Keywords: Digraphs, Polynomial Kernel, In-branching, Out-Branching}
}
|
Keywords: |
|
Digraphs, Polynomial Kernel, In-branching, Out-Branching |
|
Collection: |
|
29th Annual European Symposium on Algorithms (ESA 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
31.08.2021 |
