2021/05/04 by Stéphane Bessy, Bessy, Stéphane, Florian Hörsch +7
Computer Science · #05C20 #68Q27 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Interconnection Networks and Systems
paper · pdf · doi:10.48550/arxiv.2105.01582
openalex publication_date 2021/05/04 · openalex created_date 2021/05/10 · openalex updated_date 2026/08/01
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.