Finding Maximum Edge-Disjoint Paths Between Multiple Terminals

DOI10.1137/22M1494804MaRDI QIDQ6057790zbMATH OpenFDO

Authors Satoru Iwata, Yu Yokoi

Publication date 26 October 2023

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

blossom algorithmcombinatorial optimizationmulticommodity flow

Mathematics Subject Classification ID

Paths and cycles (05C38) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27)

Abstract: Let $G=(V,E)$ be a multigraph with a set $TsubseteqV$ of terminals. A path in $G$ is called a $T$-path if its ends are distinct vertices in $T$ and no internal vertices belong to $T$. In 1978, Mader showed a characterization of the maximum number of edge-disjoint $T$-paths. In this paper, we provide a combinatorial, deterministic algorithm for finding the maximum number of edge-disjoint $T$-paths. The algorithm adopts an augmenting path approach. More specifically, we utilize a new concept of short augmenting walks in auxiliary labeled graphs to capture a possible augmentation of the number of edge-disjoint $T$-paths. To design a search procedure for a short augmenting walk, we introduce blossoms analogously to the matching algorithm of Edmonds (1965). When the search procedure terminates without finding a short augmenting walk, the algorithm provides a certificate for the optimality of the current edge-disjoint $T$-paths. From this certificate, one can obtain the Edmonds--Gallai type decomposition introduced by SebH{o} and SzegH{o} (2004). The algorithm runs in $O(|E{|}^2)$ time, which is much faster than the best known deterministic algorithm based on a reduction to linear matroid parity. We also present a strongly polynomial algorithm for the maximum integer free multiflow problem, which asks for a nonnegative integer combination of $T$-paths maximizing the sum of the coefficients subject to capacity constraints on the edges.

Recommendations

• Maximum number of disjoint paths connecting specified terminals in a graph
• A fast algorithm for the path 2-packing problem
• On extremal multiflows
• A linear programming formulation of Mader's edge-disjoint paths problem
• On the disjoint paths problem

Cites work

• A Blossom Algorithm for Maximum Edge-Disjoint T-Paths
• A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• A linear programming formulation of Mader's edge-disjoint paths problem
• A linear-time algorithm for a special case of disjoint set union
• A short proof of Mader's \(\mathcal S\)-paths theorem
• Algebraic algorithms for linear matroid parity problems
• An algorithm for packing non-zero \(A\)-paths in group-labelled graphs
• An augmenting path algorithm for linear matroid parity
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• scientific article; zbMATH DE number 3141016 (Why is no real title available?)
• scientific article; zbMATH DE number 3550435 (Why is no real title available?)
• Integer Programming and Combinatorial Optimization
• Matroid matching and some applications
• Max flows in O(nm) time, or better
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
• Multiflows and disjoint paths of minimum total cost
• On some connectivity properties of Eulerian graphs
• Paths, Trees, and Flowers
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Some new results on node-capacitated packing of A-paths
• The Factorization of Linear Graphs
• Tree metrics and edge-disjoint \(S\)-paths
• Über die Maximalzahl kantendisjunkter A-Wege
• Über die Maximalzahl kreuzungsfreier H-Wege

Cited in

(2)

• Maximum number of disjoint paths connecting specified terminals in a graph
• Exact counting of subtrees with diameter no more than d in trees: a generating function approach

This page was built for publication: Finding Maximum Edge-Disjoint Paths Between Multiple Terminals

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