 |
 |
Reports
On the characterization of networks with multiple arc-disjoint branching flows
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.
https://hal.inria.fr/hal-03031759
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
Long-term archiving on: : Monday, March 1, 2021 - 7:38:12 PM
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
Long-term archiving on: : Monday, March 1, 2021 - 7:38:12 PM
File
Conjecture_results.pdf
Files produced by the author(s)