Characterizing Networks Admitting k Arc-disjoint Branching Flows
Resumo
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.
Referências
Bang-Jensen, J., Havet, F., and Yeo, A. (2016). The complexity of finding arc-disjoint branching flows. Discrete Applied Mathematics, 209:16–26.
Costa, J., Sales, C. L., Lopes, R., and Maia, A. K. (2019). Um estudo de redes com fluxos ramificados arco-disjuntos. Matemática Contemporânea, 46:230–238.
Edmonds, J. (1973). Edge-disjoint branchings. Combinatorial Algorithms.
Ford, L. R. and Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8:399–404.
Impagliazzo, R., Paturi, R., and Zane, F. (2001). Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512–530.
