Arc-Disjoint Branching Flows in Restricted-Capacity Networks
Abstract
The problem of determining if a given network has a feasible flow is largely studied and known to be polynomial-time solvable. In this work, we consider an specific type of flow, called branching flow, which can be useful for finding branchings in digraphs. We focus on the problem of finding multiple arc-disjoint branching flows on a given network and we study its complexity on networks with different capacities on the arcs. A previous result shows that, under a common theoretical assumption (ETH), in networks with n vertices where all the arcs have capacity equal to n−f(n), for a bounded function f, this problem is hard. We extended this result showing that, under the same assumption, the problem is also hard when the capacities are equal to f(n).
References
Bang-Jensen, J. and Bessy, S. (2014). (Arc-) disjoint flows in networks. Theoretical Computer Science, 526:28–40.
Bang-Jensen, J. and Gutin, G. Z. (2008). Digraphs: theory, algorithms and applications. Springer Science & Business Media.
Bang-Jensen, J., Havet, F., and Yeo, A. (2016). The complexity of finding arc-disjoint branching flows. Discrete Applied Mathematics, 209:16–26.
Bang-Jensen, J. and Yeo, A. (2015). Balanced branchings in digraphs. Theoretical Computer Science, 595:107 – 119.
Edmonds, J. (1973). Edge-disjoint branchings. Combinatorial Algorithms, pages 91–96.
Fortune, S., Hopcroft, J., and Wyllie, J. (1980). The directed subgraph homeomorphism problem. Theoretical Computer Science, 10(2):111 – 121.
Impagliazzo, R., Paturi, R., and Zane, F. (2001). Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512 – 530.
Lovász, L. (1976). On two minimax theorems in graph. Journal of Combinatorial Theory, Series B, 21(2):96 – 103.
