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

DOI10.1016/J.DAM.2023.11.026arXiv2105.01582MaRDI QIDQ6153458FDOQ6153458

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)

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.

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

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

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)

Cites Work

• Which problems have strongly exponential complexity?
• Connections in combinatorial optimization
• On the Problem of Decomposing a Graph into n Connected Factors
• Parameterized algorithms
• Digraphs
• On the complexity of \(k\)-SAT
• Balanced branchings in digraphs
• (Arc-)disjoint flows in networks
• The complexity of finding arc-disjoint branching flows
• Title not available (Why is that?)
• Connectivity in digraphs

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)