(Arc-)disjoint (branching) flows in networks}
Graphs, Hypergraphs, and Computing
17 April 14:00 - 15:00
Joergen Bang-Jensen - University of Southern Denmark
We consider the problem of deciding whether a given network N with integer capacities has two feasible flows x and y with prescribed balance vectors such that the set of arcs that carry flow in x is disjoint from the set of arcs that carry flow in y. This generalizes a number of well-studied problems such as 1. The existence of arc-disjoint out-branchings B_1,B_2 in a digraph, where the roots s,t of B_1, respectively B_2 may be the same vertex. 2. The existence of arc-disjoint spanning subdigraphs D_1, D_2 with prescribed degree sequences in a digraph (e.g. arc-disjoint cycle factors). 3. The weak-2-linkage problem 4. The number partitioning problem etc. Hence the problem is NP-complete in general. The problem remains hard even for very restricted cases. On the positive side, we prove that the above problem is polynomially solvable if the network is acyclic and the arc capacities as well as the desired flow values are bounded. Our algorithm for this case generalizes the algorithm (by Perl and Shiloach for k=2 and Fortune Hopcroft and Wyllie for k>=3) for the k-linkage problem in acyclic digraphs. Besides, the problem is polynomial in general digraphs if all capacities are one and the two flows have the same balance for all vertices in N, but remains NP-complete if the network contains at least one arc with capacity 2 (and the others have capacity 1). We will discuss in some detail the special case of branching flows (one root wants to send one unit of flow to all other vertices). It turns out that interesting things can be said about the complexity of deciding the existence of two arc-disjoint branching flows, depending of the capacitites of the arcs in the network. Joint work with Stephane Bessy, AlGCo, LIRMM, Universite Montpellier 2, France, Frederic Havet, INRIA Project Coati, Sophia Antipolis, France and Anders Yeo, Singapore University of Technology, Singapore.
Magnus M. Halldorsson
Adam Mickiewicz University
Technical University of Denmark, DTU