The complexity of finding arc-disjoint branching flows

The concept of arc-disjoint flows in networks was recently introduced in Bang-Jensen and Bessy (2014). This is a very general framework within which many well-known and important problems can be formulated. In particular, the existence of arc-disjoint branching flows, that is, flows which send one unit of flow from a given source ss to all other vertices, generalizes the concept of arc-disjoint out-branchings (spanning out-trees) in a digraph. A pair of out-branchings Bs,1+,Bs,2+ from a root ss in a digraph D=(V,A)D=(V,A) on nn vertices corresponds to arc-disjoint branching flows x1,x2x1,x2 (the arcs carrying flow in xixi are those used in Bs,i+, i=1,2i=1,2) in the network that we obtain from DD by giving all arcs capacity n−1n−1. It is then a natural question to ask how much we can lower the capacities on the arcs and still have, say, two arc-disjoint branching flows from the given root ss. We prove that for every fixed integer k≥2k≥2 it is •an NP-complete problem to decide whether a network N=(V,A,u)N=(V,A,u) where uij=kuij=k for every arc ijij has two arc-disjoint branching flows rooted at ss.•a polynomial problem to decide whether a network N=(V,A,u)N=(V,A,u) on nn vertices and uij=n−kuij=n−k for every arc ijij has two arc-disjoint branching flows rooted at ss. The algorithm for the later result generalizes the polynomial algorithm, due to Lovász, for deciding whether a given input digraph has two arc-disjoint out-branchings rooted at a given vertex. Finally we prove that under the so-called Exponential Time Hypothesis (ETH), for every ϵ>0ϵ>0 and for every k(n)k(n) with (log(n))1+ϵ≤k(n)≤n2 (and for every large ii we have k(n)=ik(n)=i for some nn) there is no polynomial algorithm for deciding whether a given digraph contains two arc-disjoint branching flows from the same root so that no arc carries flow larger than n−k(n)n−k(n).