The complexity of finding arc-disjoint branching flows

J. Bang-Jensen*, Frédéric Havet, Anders Yeo

*Corresponding author for this work

Research output: Contribution to journalConference articleResearchpeer-review

Abstract

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 s 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 s in a digraph D=(V,A) on n vertices corresponds to arc-disjoint branching flows x1,x2 (the arcs carrying flow in xi are those used in Bs,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≥2 it is •an NP-complete problem to decide whether a network N=(V,A,u) where uij=k for every arc ij has two arc-disjoint branching flows rooted at s.•a polynomial problem to decide whether a network N=(V,A,u) on n vertices and uij=n-k for every arc ij has two arc-disjoint branching flows rooted at s. 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 ε(lunate)>0 and for every k(n) with (log(n))1+ε(lunate)≤k(n)≤n2 (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 two arc-disjoint branching flows from the same root so that no arc carries flow larger than n-k(n).

Original languageEnglish
JournalDiscrete Applied Mathematics
Volume209
Issue numberC
Pages (from-to)16-26
ISSN0166-218X
DOIs
Publication statusPublished - 2016
Event9th International Colloquium on Graph Theory and Combinatorics - Grenoble, France
Duration: 30. Jun 20144. Jul 2014
http://oc.inpg.fr/conf/icgt2014/

Conference

Conference9th International Colloquium on Graph Theory and Combinatorics
CountryFrance
CityGrenoble
Period30/06/201404/07/2014
Internet address

Fingerprint

Branching
Disjoint
Arc of a curve
Polynomials
Computational complexity
Digraph
Polynomial Algorithm
Roots
Generalise
Exponential time
NP-complete problem

Keywords

  • Branching flow
  • Disjoint branchings
  • NP-complete
  • Polynomial algorithm

Cite this

@inproceedings{695488131fbb461b9a4c30d7ba3e8ea6,
title = "The complexity of finding arc-disjoint branching flows",
abstract = "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 s 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 s in a digraph D=(V,A) on n vertices corresponds to arc-disjoint branching flows x1,x2 (the arcs carrying flow in xi are those used in Bs,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≥2 it is •an NP-complete problem to decide whether a network N=(V,A,u) where uij=k for every arc ij has two arc-disjoint branching flows rooted at s.•a polynomial problem to decide whether a network N=(V,A,u) on n vertices and uij=n-k for every arc ij has two arc-disjoint branching flows rooted at s. The algorithm for the later result generalizes the polynomial algorithm, due to Lov{\'a}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 ε(lunate)>0 and for every k(n) with (log(n))1+ε(lunate)≤k(n)≤n2 (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 two arc-disjoint branching flows from the same root so that no arc carries flow larger than n-k(n).",
keywords = "Branching flow, Disjoint branchings, NP-complete, Polynomial algorithm",
author = "J. Bang-Jensen and Fr{\'e}d{\'e}ric Havet and Anders Yeo",
year = "2016",
doi = "10.1016/j.dam.2015.10.012",
language = "English",
volume = "209",
pages = "16--26",
journal = "Discrete Applied Mathematics",
issn = "0166-218X",
publisher = "Elsevier",
number = "C",

}

The complexity of finding arc-disjoint branching flows. / Bang-Jensen, J.; Havet, Frédéric; Yeo, Anders.

In: Discrete Applied Mathematics, Vol. 209, No. C, 2016, p. 16-26.

Research output: Contribution to journalConference articleResearchpeer-review

TY - GEN

T1 - The complexity of finding arc-disjoint branching flows

AU - Bang-Jensen, J.

AU - Havet, Frédéric

AU - Yeo, Anders

PY - 2016

Y1 - 2016

N2 - 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 s 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 s in a digraph D=(V,A) on n vertices corresponds to arc-disjoint branching flows x1,x2 (the arcs carrying flow in xi are those used in Bs,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≥2 it is •an NP-complete problem to decide whether a network N=(V,A,u) where uij=k for every arc ij has two arc-disjoint branching flows rooted at s.•a polynomial problem to decide whether a network N=(V,A,u) on n vertices and uij=n-k for every arc ij has two arc-disjoint branching flows rooted at s. 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 ε(lunate)>0 and for every k(n) with (log(n))1+ε(lunate)≤k(n)≤n2 (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 two arc-disjoint branching flows from the same root so that no arc carries flow larger than n-k(n).

AB - 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 s 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 s in a digraph D=(V,A) on n vertices corresponds to arc-disjoint branching flows x1,x2 (the arcs carrying flow in xi are those used in Bs,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≥2 it is •an NP-complete problem to decide whether a network N=(V,A,u) where uij=k for every arc ij has two arc-disjoint branching flows rooted at s.•a polynomial problem to decide whether a network N=(V,A,u) on n vertices and uij=n-k for every arc ij has two arc-disjoint branching flows rooted at s. 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 ε(lunate)>0 and for every k(n) with (log(n))1+ε(lunate)≤k(n)≤n2 (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 two arc-disjoint branching flows from the same root so that no arc carries flow larger than n-k(n).

KW - Branching flow

KW - Disjoint branchings

KW - NP-complete

KW - Polynomial algorithm

U2 - 10.1016/j.dam.2015.10.012

DO - 10.1016/j.dam.2015.10.012

M3 - Conference article

VL - 209

SP - 16

EP - 26

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - C

ER -