Abstract
Unlike the problem of deciding whether a digraph D = (V,A) has ? inbranchings (or ? outbranchings) is polynomial time solvable, the problem of deciding whether a digraph D = (V,A) has an inbranching B^ and an outbranching B^+ which are arcdisjoint is NPcomplete. Motivated by this, a natural optimization question that has been studied in the realm of Parameterized Complexity is called Rooted kDistinct 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 inbranching rooted at t and an outbranching rooted at s such that they differ on at least k arcs. BangJensen 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 kDistinct Branchings. In particular, we obtain the following: Given an instance (D,k,s,t) of Rooted kDistinct Branchings, in polynomial time we obtain an equivalent instance (D',k',s,t) of Rooted kDistinct 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 inbranching or outbranching. This result might turn out to be useful for getting other results for problems concerning inand outbranchings.
BibTeX  Entry
@InProceedings{bangjensen_et_al:LIPIcs.ESA.2021.11,
author = {BangJensen, J{\o}rgen and Klinkby, Kristine Vitting and Saurabh, Saket},
title = {{kDistinct Branchings Admits a Polynomial Kernel}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {11:111:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772044},
ISSN = {18688969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14592},
URN = {urn:nbn:de:0030drops145925},
doi = {10.4230/LIPIcs.ESA.2021.11},
annote = {Keywords: Digraphs, Polynomial Kernel, Inbranching, OutBranching}
}
Keywords: 

Digraphs, Polynomial Kernel, Inbranching, OutBranching 
Collection: 

29th Annual European Symposium on Algorithms (ESA 2021) 
Issue Date: 

2021 
Date of publication: 

31.08.2021 