Characterizing Networks Admitting k Arc-disjoint Branching Flows

  • Cláudio Carvalho UFC
  • Jonas Costa UFC
  • Raul Lopes UFC
  • Ana Karolina Maia UFC
  • Nicolas Nisse INRIA-CNRS
  • Cláudia Linhares Sales UFC

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.

Palavras-chave: fluxos, fluxos ramificados, fluxos ramificados arco-disjuntos

Referências

Bang-Jensen, J. and Bessy, S. (2014). (Arc-)disjoint flows in networks. Theoretical Computer Science, 526:28–40.

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.
Publicado
30/06/2020
CARVALHO, Cláudio; COSTA, Jonas; LOPES, Raul; MAIA, Ana Karolina; NISSE, Nicolas; SALES, Cláudia Linhares. Characterizing Networks Admitting k Arc-disjoint Branching Flows. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 5. , 2020, Cuiabá. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2020 . p. 57-60. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2020.11089.