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.