FPT algorithms for packing k-safe spanning rooted sub(di)graphs

DOI10.1016/J.DAM.2023.11.026MaRDI QIDQ6153458zbMATH OpenFDO

Authors Stéphane Bessy, Florian Hoersch, Ana Karolinna Maia, Dieter Rautenbach, Ignasi Sau

Publication date 14 February 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2105.01582

zbMATH Keywords

digraphsfixed-parameter tractabilityparameterized complexitypacking problemsarborescencesbranching flowssafe spanning trees

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We study three problems introduced by Bang-Jensen and Yeo [Theor. Comput. Sci. 2015] and by Bang-Jensen, Havet, and Yeo [Discret. Appl. Math. 2016] about finding disjoint "balanced" spanning rooted substructures in graphs and digraphs, which generalize classic packing problems. Namely, given a positive integer $k$, a digraph $D=(V,A)$, and a root $rinV$, we consider the problem of finding two arc-disjoint $k$-safe spanning $r$-arborescences and the problem of finding two arc-disjoint $(r,k)$-flow branchings. We show that both these problems are FPT with parameter $k$, improving on existing XP algorithms. The latter of these results answers a question of Bang-Jensen, Havet, and Yeo [Discret. Appl. Math. 2016]. Further, given an integer $k$, a graph $G=(V,E)$, and $rinV$, we consider the problem of finding two arc-disjoint $(r,k)$-safe spanning trees. We show that this problem is also FPT with parameter $k$, 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 $k$, which may be of independent interest.

Recommendations

• Parameterized algorithms for non-separating trees and branchings in digraphs
• K-distinct branchings admits a polynomial kernel
• k-distinct in- and out-branchings in digraphs
• \(k\)-distinct in- and out-branchings in digraphs
• Packing branchings under cardinality constraints on their root sets

Cites work

• scientific article; zbMATH DE number 3488914 (Why is no real title available?)
• (Arc-)disjoint flows in networks
• Balanced branchings in digraphs
• Connections in combinatorial optimization
• Connectivity in digraphs
• Digraphs
• On the Problem of Decomposing a Graph into n Connected Factors
• On the complexity of \(k\)-SAT
• Parameterized algorithms
• The complexity of finding arc-disjoint branching flows
• Which problems have strongly exponential complexity?

Cited in

(1)

• Constrained flows in networks

This page was built for publication: FPT algorithms for packing \(k\)-safe spanning rooted sub(di)graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6153458)