Revised: May 17, 2017

Published: December 24, 2017

**Keywords:**algorithms, complexity theory, multiflow, network flow, unsplittable flow, confluent flow, priority flow

**ACM Classification:**G.1.6, G.2.2

**AMS Classification:**68Q17, 68W25, 68Q25

**Abstract:**
[Plain Text Version]

While the maximum single-sink unsplittable and confluent flow problems
have been studied extensively, algorithmic work has been primarily
restricted to the case where one imposes the *no-bottleneck assumption*
$(\nba)$ (that the maximum demand $d_{\max}$ is at most the minimum
capacity $u_{\min}$). For instance, under the $\nba$ there is a factor-$4.43$
approximation algorithm due to Dinitz et al. (1999) for the unsplittable
flow problem.
Under the even stronger assumption of uniform capacities, there is a
factor-$3$ approximation algorithm due to Chen et al. (2007) for the
confluent flow problem.
We show, however, that unlike the unsplittable flow problem, a
constant-factor approximation algorithm cannot be obtained for the
single-sink confluent flow problem even *with* the no-bottleneck
assumption. Specifically, we prove that it is $\np$-hard to
approximate single-sink confluent flow to within
$O(\log^{1-\epsilon}(n))$, for any $\epsilon> 0$.

The remainder of our results focus upon the setting *without*
the no-bottleneck assumption. Using exponential-size demands,
Azar and Regev prove a $\Omega(m^{1-\epsilon})$ inapproximability
result for maximum cardinality single-sink unsplittable flow in
directed graphs. We prove that this lower bound applies to
undirected graphs, including planar networks (and for confluent flow).
This is the first super-constant hardness known for undirected
single-sink unsplittable flow.
Furthermore, we show $\Omega(m^{1/2-\epsilon})$-hardness
even if all demands
and capacities lie within an arbitrarily small range $[1,1+\Delta]$,
for $\Delta > 0$. This result is sharp in that if $\Delta=0$,
then it becomes a single-sink maximum edge-disjoint paths problem
which can be solved exactly via a maximum flow algorithm. This
motivates us to study maximum *priority flows* for which
we show the same inapproximability bound.