Till innehåll på sidan

Joergen Bang-Jensen: (Arc-)disjoint (branching) flows in networks

Tid: To 2014-04-17 kl 14.00 - 15.00

Plats: Institut Mittag-Leffler, Auravägen 17, Djursholm

Medverkande: Joergen Bang-Jensen, University of Southern Denmark

Exportera till kalender

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₁, B₂ in a digraph, where the roots s, t of B₁, respectively B₂ may be the same vertex.
  2. The existence of arc-disjoint spanning subdigraphs D₁, D₂ 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.