Characterizing Networks Admitting k Arc-disjoint Branching Flows - Carvalho, Cláudio; Costa, Jonas; Lopes, Raul; Maia, Ana Karolina; Nisse, Nicolas; Sales, Cláudia Linhares (Anais do Encontro de Teoria da Computação (ETC); 2020: Anais do V Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2020.11089, 2020)
An s-branching flow f in a network N = (D,c) (where c 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. In other words, the difference between the flow entering a vertex v and a flow leaving a vertex v is one whenever v is different from s. It is known that the hardness of the problem of finding k arc-disjoint s-branching flows in network N is linked to the capacity c of the arcs in N: the problem is solvable in polynomial time if every arc has capacity n - l, for fixed l, and NP-complete in most other cases, with very few cases open. We further investigate a conjecture by Costa et al. from 2019 that aims to characterize networks admitting k arc-disjoint s-branching flows, generalizing a classical result by Edmonds that provides such characterization when all arcs have capacity n-1. We show that, in general, the conjecture is false. However, on the positive side, it holds for digraphs formed by out-branchings together with parallel arcs.