Revised: May 17, 2017
Published: December 24, 2017
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.