Theory of Computing
-------------------
Title     : The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems
Authors   : F. Bruce Shepherd and Adrian R. Vetta
Volume    : 13
Number    : 20
Pages     : 1-25
URL       : https://theoryofcomputing.org/articles/v013a020

Abstract
--------

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.