pdf icon
Volume 13 (2017) Article 20 pp. 1-25
The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems
Received: September 18, 2015
Revised: May 17, 2017
Published: December 24, 2017
Download article from ToC site:
[PDF (862K)] [PS (9211K)] [Source ZIP]
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]

$ \newcommand{\nba}{\text{nba}} \newcommand{\np}{\textsf{NP}} $

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.