FPT algorithms for packing $k$-safe spanning rooted sub(di)graphs
Stéphane Bessy, Florian Hörsch, Ana Karolinna Maia, Dieter Rautenbach, Ignasi Sau · arXiv (Cornell University) · 2021
We study three problems introduced by Bang-Jensen and Yeo (2015) and by Bang-Jensen et al. (2016) about finding disjoint “balanced” spanning rooted substructures in graphs and digraphs, which generalize classic packing problems such as detecting the existence of multiple arc-disjoint spanning arborescences. Namely, given a positive integer , a digraph , and a root , we first consider the problem of finding two arc-disjoint -safe spanning -arborescences, meaning arborescences rooted at a vertex such that deleting any arc and every vertex in the sub-arborescence rooted at leaves at least vertices. Then, we consider the problem of finding two arc-disjoint -flow branchings meaning arc sets admitting a flow that distributes one unit from to every other vertex while respecting a capacity limit of on every arc. We show that both these problems are FPT with parameter , improving on existing XP algorithms. The latter of these results answers a question of Bang-Jensen et al. (2016). Further, given a positive integer , a graph , and , we consider the problem of finding two edge-disjoint -safe spanning trees meaning spanning trees such that the component containing has size at least when deleting any vertex different from . We show that this problem is also FPT with parameter , again improving on a previous XP algorithm. Our main technical contribution is to prove that the existence of such spanning substructures is equivalent to the existence of substructures with size and maximum (out-)degree both bounded by a (linear or quadratic) function of , which may be of independent interest.