Skip to Main content Skip to Navigation

On the characterization of networks with multiple arc-disjoint branching flows

Cláudio Carvalho 1, 2 Jonas Costa 1, 2 Cláudia Sales 1, 2 Raul Lopes 1, 2 Ana Karolinna Maia de Oliveira 1, 2, 3 Nicolas Nisse 4
3 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
4 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : An s-branching flow f in a network N = (D, u), such that u is the capacity function, is a flow that reaches every vertex in V (D) \ {s} from s while loosing exactly one unit of flow in each vertex other than s. It is known that the hardness of the problem of finding k arc-disjoint s-branching flows in a network N is linked to the capacity u of the arcs in N : for fixed c, the problem is solvable in polynomial time if every arc has capacity n − c and, unless the Exponential Time Hypothesis (ETH) fails, there is no polynomial time algorithm for it for most other choices of the capacity function when every arc has the same capacity. The hardness of a few cases remains open. We further investigate a conjecture that aims to characterize networks admitting k arc-disjoint s-branching flows, generalizing a result that provides such characterization when all arcs have capacity n−1, based on Edmonds' branching theorem. We show that, in general, the conjecture is false. However, it holds for some special classes of digraphs, as branchings and spindles with parallel arcs.
Complete list of metadatas
Contributor : Ana Karolinna Maia <>
Submitted on : Monday, November 30, 2020 - 3:58:59 PM
Last modification on : Thursday, January 21, 2021 - 1:34:13 PM


Files produced by the author(s)


  • HAL Id : hal-03031759, version 1


Cláudio Carvalho, Jonas Costa, Cláudia Sales, Raul Lopes, Ana Karolinna Maia de Oliveira, et al.. On the characterization of networks with multiple arc-disjoint branching flows. [Research Report] UFC; INRIA; CNRS; Université Côte d’Azur; I3S; LIRMM; Université de Montpellier. 2020. ⟨hal-03031759⟩



Record views


Files downloads