Cláudio Carvalho ; Jonas Costa ; Raul Lopes ; Ana Karolinna Maia ; Nicolas Nisse et al. - From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flows

dmtcs:9302 - Discrete Mathematics & Theoretical Computer Science, May 2, 2023, vol. 25:1 - https://doi.org/10.46298/dmtcs.9302
From branchings to flows: a study of an Edmonds' like property to arc-disjoint branching flowsArticle

Authors: Cláudio Carvalho 1,2; Jonas Costa 1,2; Raul Lopes ORCID3; Ana Karolinna Maia ORCID4,1; Nicolas Nisse ORCID5,6,7,8; Cláudia Sales 1,2

An s-branching flow f in a network N = (D, u), where u is the capacity function, is a flow thatreaches every vertex in V(D) from s while loosing exactly one unit of flow in each vertex other thans. Bang-Jensen and Bessy [TCS, 2014] showed that, when every arc has capacity n − 1, a network Nadmits k arc-disjoint s-branching flows if and only if its associated digraph D contains k arc-disjoints-branchings. Thus a classical result by Edmonds stating that a digraph contains k arc-disjoints-branchings if and only if the indegree of every set X ⊆ V (D) \ {s} is at least k also characterizesthe existence of k arc-disjoint s-branching flows in those networks, suggesting that the larger thecapacities are, the closer an s-branching flow is from simply being an s-branching. This observationis further implied by results by Bang-Jensen et al. [DAM, 2016] showing that there is a polynomialalgorithm to find the flows (if they exist) when every arc has capacity n − c, for every fixed c ≥ 1,and that such an algorithm is unlikely to exist for most other choices of the capacities. In this paper,we investigate how a property that is a natural extension of the characterization by Edmonds’ relatesto the existence of k arc-disjoint s-branching flows in networks. Although this property is alwaysnecessary for the existence of the flows, we show that it is not always sufficient and that it is hardto decide if the desired flows exist even if we know beforehand that the network satisfies it. On thepositive side, we show that it guarantees the existence of the desired flows in some particular casesdepending on the choice of the capacity function or on the structure of the underlying graph of D,for example. We remark that, in those positive cases, polynomial time algorithms to find the flowscan be extracted from the constructive proofs.


Volume: vol. 25:1
Section: Graph Theory
Published on: May 2, 2023
Accepted on: March 10, 2023
Submitted on: April 4, 2022
Keywords: Digraphs,Branchings,Branching flows,Arc-disjoint flows,[MATH]Mathematics [math],[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC],[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : HAL
  • Digraphes; Funder: French National Research Agency (ANR); Code: ANR-19-CE48-0013
  • Idex UCA JEDI; Funder: French National Research Agency (ANR); Code: ANR-15-IDEX-0001
  • Algorithmes avec décomposition moins connu: graphes et matroids; Funder: French National Research Agency (ANR); Code: ANR-18-CE40-0025

Consultation statistics

This page has been seen 680 times.
This article's PDF has been downloaded 477 times.