# The complexity of finding arc-disjoint branching flows

2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : The concept of arc-disjoint flows in networks was recently introduced in \cite{bangTCSflow}. 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 $s$ to all other vertices, generalizes the concept of arc-disjoint out-branchings (spanning out-trees) in a digraph. A pair of out-branchings $B_{s,1}^+,B_{s,2}^+$ from a root $s$ in a digraph $D=(V,A)$ on $n$ vertices corresponds to arc-disjoint branching flows $x_1,x_2$ (the arcs carrying flow in $x_i$ are those used in $B_{s,i}^+$, $i=1,2$) in the network that we obtain from $D$ by giving all arcs capacity $n-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 $s$.We prove that for every fixed integer $k \geq 2$ it is\begin{itemize}\item an NP-complete problem to decide whether a network ${\cal N}=(V,A,u)$ where $u_{ij}=k$ for every arc $ij$ has two arc-disjoint branching flows rooted at $s$.\item a polynomial problem to decide whether a network ${\cal N}=(V,A,u)$ on $n$ vertices and $u_{ij}=n-k$ for every arc $ij$ has two arc-disjoint branching flows rooted at $s$.\end{itemize}The algorithm for the later result generalizes the polynomial algorithm, due to Lov\'asz, 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 $\epsilon{}>0$ and for every $k(n)$ with $(\log{}(n))^{1+\epsilon}\leq k(n)\leq \frac{n}{2}$ (and for every large $i$ we have $k(n)=i$ for some $n$) there is no polynomial algorithm for deciding whether a given digraph contains twoarc-disjoint branching flows from the same root so that no arc carries flow larger than $n-k(n)$.
Keywords :
Type de document :
Rapport
[Research Report] RR-8640, INRIA Sophia Antipolis; INRIA. 2014
Domaine :

Littérature citée [12 références]

https://hal.inria.fr/hal-01088664
Contributeur : Frederic Havet <>
Soumis le : vendredi 28 novembre 2014 - 13:32:26
Dernière modification le : mercredi 31 janvier 2018 - 10:24:05
Document(s) archivé(s) le : vendredi 14 avril 2017 - 23:01:46

### Fichier

RR-8640.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-01088664, version 1

### Citation

Joergen Bang-Jensen, Frédéric Havet, Anders Yeo. The complexity of finding arc-disjoint branching flows. [Research Report] RR-8640, INRIA Sophia Antipolis; INRIA. 2014. 〈hal-01088664〉

### Métriques

Consultations de la notice

## 298

Téléchargements de fichiers