The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems

Authors F. Bruce Shepherd, Adrian R. Vetta,

Plaintext

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25
www.theoryofcomputing.org

The Inapproximability of Maximum
Single-Sink Unsplittable, Priority and
Confluent Flow Problems
F. Bruce Shepherd∗ Adrian R. Vetta†
Received September 18, 2015; Revised May 17, 2017; Published December 24, 2017

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 dmax is at most the
minimum capacity umin ). 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(log1−ε (n)),
for any ε > 0.
The remainder of our results focus upon the setting without the no-bottleneck assumption.
Using exponential-size demands, Azar and Regev prove a Ω(m1−ε ) inapproximability result
for maximum cardinality single-sink unsplittable flow in directed graphs. We prove that this
∗ Supported by an NSERC Discovery Research Grant.
† Supported by an NSERC Discovery Research Grant.

ACM Classification: G.1.6, G.2.2
AMS Classification: 68Q17, 68W25, 68Q25
Key words and phrases: algorithms, complexity theory, multiflow, network flow, unsplittable flow,
confluent flow, priority flow

© 2017 F. Bruce Shepherd and Adrian R. Vetta
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2017.v013a020
F. B RUCE S HEPHERD AND A DRIAN R. V ETTA

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 Ω(m1/2−ε )-hardness even if all demands and capacities lie within
an arbitrarily small range [1, 1 + ∆], for ∆ > 0. This result is sharp in that if ∆ = 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.

1 Introduction
In this paper we improve known lower bounds (and upper bounds) on the approximability of the
maximization versions of the single-sink unsplittable flow, single-sink priority flow and single-sink
confluent flow problems. In the single-sink network flow problem, we are given a directed or undirected
graph G = (V, E) with n nodes and m edges that has edge capacities u(e) or node capacities u(v). There
are a collection of demands that have to be routed to a unique destination sink node t. Each demand i is
located at a source node si (multiple demands could share the same source) and requests an amount di of
flow capacity in order to route. We will primarily focus on the following two well-known versions of the
single-sink network flow problem.

• Unsplittable Flow. Each demand i must be sent along a unique path Pi from si to ti .

• Confluent Flow. Any two demands that meet at a node must then traverse identical paths to the
sink. In particular, at most one edge out of each node v is allowed to carry flow. Consequently, the
support of the flow is a tree in undirected graphs, and an arborescence rooted at t in directed graphs.

Unsplittable flows were introduced in [16] to study optical (SONET) ring networks. The single-sink
version was introduced in [23, 22] and has led to a wealth of algorithmic developments. Confluent flows
were introduced to study the effects of next-hop routing [12]. In that application, routers are capacitated
and, consequently, nodes in the confluent flow problem are assumed to have capacities but not edges.
In contrast, in the unsplittable flow problem it is the edges that are assumed to be capacitated. We
follow these conventions in this paper. In addition, we also examine a third network flow problem called
Priority Flow (defined in Section 1.2). In the literature, subject to network capacities, there are two
standard maximization objectives.

• Cardinality. Maximise the total number of demands routed.

• Throughput. Maximise satisfied demand, that is, the total flow carried by the routed demands.

These objectives can be viewed as special cases of the profit-maximisation flow problem. There each
demand i has a profit πi in addition to its demand di . The goal is to route a subset of the demands of
maximum total profit. The cardinality model then corresponds to the unit-profit case, wi = 1 for every
demand i; the throughput model is the case πi = di . Clearly the lower bounds we will present also apply
to the more general profit-maximisation problem.

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 2
I NAPPROXIMABILITY OF U NSPLITTABLE , P RIORITY AND C ONFLUENT F LOW

1.1 Previous work
The unsplittable flow problem has been extensively studied since its introduction by Cosares and
Saniee [16] and Kleinberg [23]. However, most positive results have relied upon the no-bottleneck
assumption (NBA) where the maximum demand is at most the minimum capacity, that is, dmax ≤ umin .
Given the NBA, the best known result is a factor-4.43 approximation algorithm due to Dinitz, Garg and
Goemans [17] for the maximum throughput objective.
The confluent flow problem was first examined by Chen, Rajaraman and Sundaram [12]. There,
and in variants of the problem [11, 18, 31], the focus was on uncapacitated graphs.1 The current best
result for maximum confluent flow is a factor-3 approximation algorithm for maximum throughput in
uncapacitated networks [11].
Observe that uncapacitated networks (i. e., graphs with uniform capacities) trivially also satisfy the
NBA. Much less is known about networks where the NBA does not hold. This is reflected by the dearth of
progress for the case of multiflows (that is, multiple sink) without the NBA. It is known that a constant-
factor approximation algorithm exists for the case in which G is a path [5], and that a poly-logarithmic
approximation algorithm exists for the case in which G is a tree [7]. The extreme difficulty of the
unsplittable flow problem is suggested by the following result of Azar and Regev [3].

Theorem 1.1 (Azar–Regev). If P 6= NP then, for any ε > 0, there is no O(m1−ε )-approximation algorithm
for the cardinality objective of the single-sink unsplittable flow problem in directed graphs.

This is the first (and only) super-constant lower bound for the maximum single-sink unsplittable flow
problem.

1.2 Our results
The main focus of this paper is on single-sink flow problems where the no-bottleneck assumption (NBA)
does not hold. It turns out that the hardness of approximation bounds are quite severe even in the (often
more tractable) single-sink setting. In some cases they match the worst case bounds for PIPs (general
packing integer programs). In particular, we strengthen Theorem 1.1 in several ways. First, as noted by
Azar and Regev, the proof of their result relies critically on having directed graphs. We prove that it holds
for undirected graphs and even planar undirected graphs. Second, we show that the result also applies to
the confluent flow problem.

Theorem 1.2. If P 6= NP then, for any ε > 0, there is no O(m1−ε )-approximation algorithm for the
cardinality objective of the maximum single-sink unsplittable and confluent flow problems in undirected
graphs. Moreover for unsplittable flows, the lower bound holds even when we restrict to planar inputs.

Third, Theorems 1.1 and 1.2 rely upon the use of exponentially large demands—we call this the
large-demand regime. A second demand scenario that has received attention in the literature is the
polynomial-demand regime. This is the regime considered in [21]. We show that strong hardness results
apply in the polynomial-demand regime; in fact, they apply to the small-demand regime where the demand
spread dmax /dmin = 1 + ∆, for some arbitrarily “small” constant ∆ > 0. (Note that dmin ≤ umin and so
1 An exception concerns the analysis of graphs with constant treewidth [19].

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 3
F. B RUCE S HEPHERD AND A DRIAN R. V ETTA

the demand spread of an instance is at least the bottleneck value dmax /umin .) In this regime we obtain
similar hardness results for the throughput objective for the single-sink unsplittable and confluent flow
problems. Formally, we show the following m1/2−ε -inapproximability result. We note however that the
hard instances have a linear number of edges so one may prefer to call this an n1/2−ε -inapproximability
result.
Theorem 1.3. If P 6= NP, then the single-sink versions of maximum unsplittable and confluent flow
problems cannot be approximated to within a factor of O(m1/2−ε ), for any ε > 0. This holds in either
the cardinality or throughput objectives and for undirected and directed graphs even when instances are
restricted to have demand spread dmax /dmin = 1 + ∆, where ∆ > 0 is an arbitrarily small constant.
Again for the unsplittable flow problem this hardness result applies even in planar graphs. Theorems 1.2
and 1.3 are the first super-constant hardness for any undirected version of the single-sink unsplittable
flow problem, and any directed version with small demands.
To clarify what is happening in our hardness results for small ∆ > 0, we introduce and examine an
intermediary problem, the maximum priority flow problem. Here, we have a graph G = (V, E) with a sink
node t, and demands from nodes si to t. These demands are unit demands, and thus ∆ = 0. However,
a demand may not traverse every edge. Specifically, we have a partition of E into k priority classes Ei .
Each demand also has a priority, and a demand of priority i may only use edges of priority i or better (i. e.,
edges in E1 ∪ E2 ∪ . . . Ei ). The goal is to find a maximum routable subset of the demands. Observe that,
for this unit-demand problem, the throughput and cardinality objectives are identical. We view this as an
intermediate problem since we can realize it as an instance of the small demand unsplittable flow problem.
We first select numbers 1 > δ1 > δ2 > · · · > δk > 0 and then set demand i to have value di = 1 + δi . We
then assign capacity 1 + δi to the edges of Ei .
Whilst various priority network design problems have been considered in the literature (cf. [6, 14]),
we are not aware of existing results on maximum priority flow. Our results immediately imply the
following.
Corollary 1.4. The single-sink maximum priority flow problem cannot be approximated to within a factor
of m1/2−ε , for any ε > 0, in planar directed or undirected graphs.
It was noted [21] that “. . . the hardness of undirected edge-disjoint paths remains an interesting
open question. Indeed, even the hardness of edge-capacitated unsplittable flow remains open.”2 A
polylogarithmic lower bound later appeared in [2] for the maximum edge-disjoint paths (MEDP) problem
(this was subsequently extended to the regime where edge congestion is allowed [1]). For the capacitated
version, our results show that unsplittable flow suffers polynomial hardness (even for single-sink instances).
Moreover, a polynomial lower bound for MEDP seems less likely given the recent O(1)-congestion
polylog-approximation algorithms [13, 15]. In this light, our hardness results for single-sink unsplittable
flow again highlight the sharp threshold involved with the NBA (or the special case of MEDP here). That is,
if we allow some slight variation in demands and capacities within a tight range [1, 1 + ∆] we immediately
jump from (plausible) polylogarithmic approximations for MEDP to (known) polynomial hardness of
the corresponding maximum unsplittable flow instances. A similar phenomenon holds for planar graphs
2 In [21], they do however establish an inapproximability bound of n1/2−ε , for any ε > 0, on node-capacitated USF in

undirected graphs.

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 4
I NAPPROXIMABILITY OF U NSPLITTABLE , P RIORITY AND C ONFLUENT F LOW

where MEDP has a constant-factor approximation with congestion 2 [10, 30] and constant-factor (with
no congestion) for high-diameter planar graphs [24]. In contrast, our results imply polynomial hardness
when some slight demand variation is allowed.
We next note that Theorems 1.1 and 1.2 are stronger than Theorem 1.3 in the sense that they have
exponents of 1 − ε rather than 1/2 − ε. Again, this extra boost is due to their use of exponential
demand sizes. One can obtain a more refined picture as to how the hardness of cardinality single-sink
unsplittable/confluent flow varies with the demand sizes, or more precisely how it varies on the bottleneck
value dmax /umin .3

Theorem 1.5. Consider any fixed ε > 0 and dmax /umin > 1. It is NP-hard p to approximate cardinality
single-sink unsplittable/confluent flow to within a factor of O(m1/2−ε · log(dmax /umin )) in undirected
or directed graphs. For unsplittable flow, this remains true for planar graphs.

Once again we see the message that there is a sharp cutoff for dmax /umin > 1 even in the large-demand
regime. This is because if the bottleneck value is at most 1, then the no-bottleneck assumption holds and,
√
consequently, the single-sink unsplittable flow problem admits a constant-factor approximation (not m
hardness). We mention that a similar hardness bound cannot hold for the maximum throughput objective,
since one can always reduce to the case where dmax /umin is small with a polylogarithmic loss, and hence
the lower bound becomes at worst O(m1/2−ε · log m). We feel the preceding hardness bound is all the
more interesting since known greedy techniques yield almost-matching upper bounds, even for general
multiflows.
√
Theorem 1.6. There is an O( m log(dmax /umin )) approximation algorithm for cardinality unsplittable
√
flow and an O( m log n) approximation algorithm for throughput unsplittable flow, in both directed and
undirected graphs.

We next focus on confluent flows assuming the NBA. Recall that for the maximum single-sink
unsplittable flow problem there is a constant-factor approximation algorithm given the NBA. This is not
the case for the single-sink confluent flow problem as we provide a super-constant lower bound. Its proof
is more complicated but builds on the techniques used for our previous results.

Theorem 1.7. Given the NBA, the single-sink confluent flow problem cannot be approximated to within
a factor O(log1−ε n), for any ε > 0, unless P = NP. This holds for both the maximum cardinality and
maximum throughput objectives in undirected and directed graphs.

An almost-matching polylogarithmic approximation has subsequently been found for maximum confluent
flow with the NBA [32].
Finally, we include a hardness result for the congestion minimization problem for confluent flows.
That is, the problem of finding the minimum value α ≥ 1 such that all demands can be routed confluently
if all node capacities are multiplied by α. This problem has two plausible variants.
3 This seems likely connected to a footnote in [3] that a lower bound of the form

p
O m1/2−ε · log(dmax /umin )

exists for maximum unsplittable flow in directed graphs. Its proof was omitted however.

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 5
F. B RUCE S HEPHERD AND A DRIAN R. V ETTA

A strong congestion algorithm is one where the resulting flow must route on a tree T such that for any
demand v the nodes on its path in T must have capacity at least d(v). A weak congestion algorithm does
not require this extra constraint on the tree capacities. Both variants are of possible interest. If the motive
for congestion is to route all demands in some limited number α of rounds of admission, then each round
should be feasible on T —hence strong congestion is necessary. On the other hand, if the objective is to
simply augment network capacity so that all demands can be routed, weak congestion is the right notion.
In Section 3.1.3 we show that it is hard to approximate strong congestion to within polynomial factors.
Theorem 1.8. It is NP-hard to approximate the minimum (strong) congestion problem for single-sink
confluent flow instances (with polynomial-size demands) to factors of at most m1/2−ε for any ε > 0.

1.3 Overview of paper
At the heart of our reductions are gadgets based upon the capacitated 2-disjoint paths problem. We
√
discuss this problem in Section 2. In Section 3, we establish a m inapproximability result for maximum
single-sink unsplittable/confluent flow in the small-demand regime (Theorem 1.3); we give a similar
hardness for single-sink priority flow (Corollary 1.4). Using a similar basic construction, we then
establish, in Section 4, a polylogarithmic inapproximability result for maximum single-sink confluent
flow even given the NBA (Theorem 1.7). In Section 5, we give lower bounds on the approximability of
the cardinality objective for general-demand regimes (Theorems 1.2 and 1.5). Finally, in Section 6, we
present an almost matching upper bound for unsplittable flow (Theorem 1.6) and priority flow.
The following two tables (Figures 1 and 2) consolidate the known inapproximability results when the
NBA is not enforced.

Undirected Directed Planar (Directed or Undirected)
M AX UFP Ω(m1−ε ) this paper Ω(m1−ε ) Azar-Regev Ω(m1−ε ) this paper
M AX C ONFLUENT Ω(m1−ε ) this paper Ω(m1−ε ) this paper NP-Hard by subset sum

Figure 1: Inapproximability results without NBA and with exponential demands.

Directed or Undirected Planar (Directed or Undirected)
M AX UFP/ Max Priority Ω(m1/2−ε ) this paper Ω(m1/2−ε ): this paper
M AX C ONFLUENT Ω(m1/2−ε ) this paper NP-hard by subset sum

Figure 2: Inapproximability results without NBA and with polynomial demands.

2 The Two-Disjoint Paths problem
Our hardness reductions require gadgets based upon the capacitated 2-disjoint paths problem. Before
describing this problem, recall the classical 2-disjoint paths problem:

2-Disjoint Paths (Uncapacitated): Given a graph G and node pairs {x1 , y1 } and {x2 , y2 }. Does
G contain paths P1 from x1 to y1 and P2 from x2 to y2 such that P1 and P2 are disjoint?

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 6
I NAPPROXIMABILITY OF U NSPLITTABLE , P RIORITY AND C ONFLUENT F LOW

Observe that this formulation incorporates four distinct problems because the graph G may be directed
or undirected and the desired paths may be edge-disjoint or node-disjoint. In undirected graphs the
2-disjoint paths problem, for both edge-disjoint and node disjoint paths, can be solved in polynomial
time—see Robertson and Seymour [29]. In directed graphs, perhaps surprisingly, the problem is NP-hard.
This is the case for both edge-disjoint and node disjoint paths, as shown by Fortune, Hopcroft and
Wyllie [20].
In general, the unsplittable and confluent flow problems concern capacitated graphs. Therefore, our
focus is on the capacitated version of the 2-disjoint paths problem.

2-Disjoint Paths (Capacitated): We are given a graph G and two parameters β ≥ α. The edges
of G are assigned capacities ∈ {α, β }. Given node pairs {x1 , y1 } and {x2 , y2 }, does G contain paths P1
from x1 to y1 and P2 from x2 to y2 such that:

(i) P1 and P2 are disjoint.

(ii) P2 may only use edges of capacity β . (P1 may use both capacity α and capacity β edges.)

For directed graphs, the result of Fortune et al. [20] immediately implies that the capacitated version
is hard—simply assume every edge has capacity β . In undirected graphs, the case of node-disjoint paths
was proven to be hard by Guruswami et al. [21]. The case of edge-disjoint paths was recently proven to
be hard by Naves, Sonnerat and Vetta [27], even in planar graphs where terminals lie on the outside face
(in an interleaved order, which will be important for us). These results are summarised in Table 1.

Directed Undirected
Node-Disjoint NP-hard [20] NP-hard [21]
Edge-Disjoint NP-hard [20] NP-hard [27]

Table 1: Hardness of the Capacitated 2-Disjoint Paths Problem.

Recall that the unsplittable flow problem has capacities on edges, whereas the confluent flow problem
has capacities on nodes. Consequently, our hardness reductions for unsplittable flows require gadgets
based upon the hardness for edge-disjoint paths [27]; for confluent flows we require gadgets based upon
the hardness for node-disjoint paths [21].

3 Polynomial hardness of single-sink unsplittable, confluent and priority
flow
In this section, we establish that the single-sink maximum unsplittable and confluent flow problems are
hard to approximate within polynomial factors for both the cardinality and throughput objectives. We
will then show how these hardness results extend to the single-sink maximum priority flow problem. We
begin with the small-demand regime by proving Theorem 1.3. Its proof introduces some core ideas that
are used in later sections in the proofs of Theorems 1.5 and 1.7.

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 7
F. B RUCE S HEPHERD AND A DRIAN R. V ETTA

s1 1+δ

1+δ
1+2δ 1+2δ
s2

1+δ 1+2δ
1+3δ 1+3δ 1+3δ
s3

1+δ 1+2δ 1+3δ

1+(N‐1)δ 1+(N‐1)δ 1+(N‐1)δ 1+(N‐1)δ
sN‐1

1+δ 1+2δ 1+3δ 1+(N‐1)δ
1+Nδ 1+Nδ 1+Nδ 1+Nδ 1+Nδ
sN

1+δ 1+2δ 1+3δ 1+(N‐1)δ 1+Nδ
t1 t2 t3 tN‐1 tN

Figure 3: A Half-Grid GN .

√
3.1 n-hardness in the small-demand regime

Our approach uses a grid routing structure much as in the hardness proofs of Guruswami et al. [21].
Specifically:
(1) We introduce a graph GN that has the following properties. There are demands with values 1 + iδ
for i = 1, . . . , N and so dmin = 1 + δ ≤ dmax = 1 + Nδ . There is a set of pairwise crossing paths that can
route demands of total value ∑Ni=1 (1 + iδ ) = N + δ (N/2)(N + 1). On the other hand, any collection of
pairwise non-crossing paths can route at most dmax = 1 + Nδ units of the total demand. For a given
∆ ∈ (0, 1) we choose δ to be small enough so that dmax ≤ 1 + ∆ < 2.
(2) We then build a new network G by replacing each node of GN by an instance of the capacitated
2-disjoint paths problem. This routing problem is chosen because it induces the following properties. If it
is a YES-instance, then a maximum unsplittable (or confluent) flow on G corresponds to routing demands
in GN using pairwise-crossing paths. In contrast, if it is a NO-instance, then a maximum unsplittable or
confluent flow on G corresponds to routing demands in GN using pairwise non-crossing paths.
Since GN contains n = O(N 2 ) nodes, it follows that an approximation algorithm with guarantee better
√
than Θ( n) allows us to distinguish between YES- and NO-instances of our routing problem, giving an
√
inapproximability lower bound of Ω( n). Furthermore, at all stages we show how this reduction can be
applied using only undirected graphs. This will prove Theorem 1.3.

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 8
I NAPPROXIMABILITY OF U NSPLITTABLE , P RIORITY AND C ONFLUENT F LOW

3.1.1 A half-grid graph GN
Let’s begin by defining the graph GN . There are N rows (numbered from top to bottom) and N columns
(numbered from left to right). We call the leftmost node in the ith row si , and the bottom node in the jth
column t j . There is a demand of size ci := 1 + iδ located at si . Recall, that δ is chosen so that all demands
and capacities lie within a tight range [1, 1 + ∆] for fixed ∆ small. All the edges in the ith row and all the
edges in the ith column have capacity ci . The ith row extends as far as the ith column and vice versa; thus,
we obtain a “half-grid" that is a weighted version of the network considered by Guruswami et al. [21].
Finally we add a sink t. There is an edge of capacity c j between t j to t. The complete construction is
shown in Figure 3.
For the unsplittable flow problem we have edge capacities. We explain later how the node capacities
are incorporated for the confluent flow problem. We also argue about the undirected and directed
reductions together. For directed instances we always enforce edge directions to be downwards and to the
right.
Note that there is a unique si − t path Pi∗ consisting only of edges of capacity ci , that is, the hooked
path that goes from si along the ith row and then down the ith column to t. We call this the canonical path
for demand i.
Claim 3.1. Take two feasible paths Qi and Q j for demands i and j. If i < j, then the paths must cross on
row j, between columns i and j − 1.
Proof. Consider demand i originating at si . This demand cannot use any edge in columns 1 to i − 1 as it
is too large. Consequently, any feasible path Qi for demand i must include all of row i. Similarly, Q j must
contain all of row j. Row j cuts off si from the sink t, so Qi must meet Q j on row j. Demand i cannot
use an edge in row j as demand j is already using up all the capacity along that row. Thus Qi crosses Q j
at the point they meet. As above, this meeting cannot occur in columns 1 to i − 1. Thus the crossing point
must occur on some column between i and j − 1 (by construction of the half-grid, column j only goes as
high as row j so the crossing cannot be there).

By Claim 3.1, if we are forced to route using pairwise non-crossing paths, then only one demand can
route. Thus we can route at most a total of cN = 1 + δ N < 2 units of demand.

3.1.2 The instance G
We build a new instance G by replacing each degree 4 node in GN with an instance of the 2-disjoint paths
problem. For the unsplittable flow problem in undirected graphs we use gadgets H corresponding to the
capacitated edge-disjoint paths problem. Observe that a node at the intersection of column i and row j
(with j > i) in GN is incident to two edges of capacity ci and to two edges of weight c j . We construct G
by replacing each such node of degree four with the routing graph H. We do this in such a way that the
capacity ci edges of GN are incident to x1 and y1 , and the c j edges are incident to x2 and y2 . We also let
α = ci and β = c j .
For the confluent flow problem in undirected graphs we now have node capacities. Hence we use
gadgets H corresponding to the node-capacitated 2-paths problem discussed above.
For directed graphs, the mechanism is simpler as the gadgets may now come from the uncapacitated
disjoint paths problem. Thus the hardness comes from the directedness and not from the capacities.

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 9
F. B RUCE S HEPHERD AND A DRIAN R. V ETTA

Specifically, we may set the edge capacities to be C = max{ci , c j }. Moreover, for unsplittable flow we
may perform the standard operation of splitting each node in H into two, with the new induced arc having
capacity of C. It follows that if there are two flow paths through H, each carrying at least ci ≥ c j flow,
then they must be from x1 to y1 and x2 to y2 . These provide a solution to the node-disjoint directed paths
problem in H.
The hardness result will follow once we see how this construction relates to crossing and non-crossing
collections of paths.

Lemma 3.2. If H is a YES-instance, then the maximum unsplittable/confluent flow in G has value at least
N. For a NO-instance the maximum unsplittable/confluent flow has value at most 1 + ∆ < 2.

Proof. If H is a YES-instance, then we can use its paths to produce paths in G, whose images in GN ,
are free to cross at any node. Hence we can produce paths in G whose images are the canonical paths
Pi∗ , 1 ≤ i ≤ N in GN . This results in a flow of value greater than N. Note that in the confluent case, these
paths yield a confluent flow as they only meet at the root t.
Now suppose H is a NO-instance. Take any flow and consider two paths Q̂i and Q̂ j in G for demands
i and j, where i < j. These paths also induce two feasible paths Qi and Q j in the half-grid GN . By
Claim 3.1, these paths cross on row j of the half-grid (between columns i and j − 1). In the directed case
(for unsplittable or confluent flow) if they cross at a grid-node v, then the paths they induce in the copy of
H at v must be node-disjoint. This is not possible in the directed case since such paths do not exist for
(x1 , y1 ) and (x2 , y2 ).
In the undirected confluent case, we must also have node-disjoint paths through this copy of H. As
we are in row j and a column between column i and j − 1, we have β = c j and ci ≤ α ≤ c j−1 . Thus,
demand j can only use the β -edges of H. This contradicts the fact that H is a NO-instance. For the
undirected case of unsplittable flow the two paths through H need to be edge-disjoint, but now we obtain
a contradiction as our gadget was derived from the capacitated edge-disjoint paths problem.
It follows that no such pair Q̂i and Q̂ j can exist and, therefore, the confluent/unsplittable flow routes
at most one demand and, hence, routes a total demand of at most 1 + ∆.

We then obtain our hardness result.
Theorem 1.3. Neither cardinality nor throughput can be approximated to within a factor of O(m1/2−ε ),
for any ε > 0, in the single-sink unsplittable and confluent flow problems. This holds for undirected and
directed graphs even when instances are restricted to have bottleneck value dmax /umin = 1 + ∆ where
∆ > 0 is arbitrarily small.

Proof. It follows that if we could approximate the maximum (unsplittable) confluent flow problem in G
to a factor better than N, we could determine whether the optimal solution is at least N or at most 1 + ∆.
This in turn would allow us to determine whether H is a YES- or a NO-instance.
Note that G has n = Θ(pN 2 ) edges, where p = |V (H)|. If we take N = Θ(p(1/2)(1/ε−1) ), where ε > 0
is an (arbitrarily) small constant, then n = p1/ε and so N = Θ(n(1/2)(1−ε) ). A precise lower bound of
0
n1/2−ε is obtained for ε 0 > ε sufficiently small, when n is sufficiently large.

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 10
I NAPPROXIMABILITY OF U NSPLITTABLE , P RIORITY AND C ONFLUENT F LOW

3.1.3 Priority flows and congestion
We now establish the hardness of priority flows. To do this, we use the same half-grid construction, except
we must replace the capacities by priorities. This is achieved in a straight-forward manner. Priorities are
defined by the magnitude of the original demands/capacities. The larger the demand or capacity in the
original instance, the higher its priority in the new instance. (Given the priority ordering we may then
assume all demands and capacities are set to 1.) In this setting, observe that Claim 3.1 also applies for
priority flows.
Claim 3.3. Consider two feasible paths Qi and Q j for demands i and j in the priority flow problem. If
i < j, then the paths must cross on row j, between columns i and j − 1.
Proof. Consider demand i originating at si . This demand cannot use any edge in columns 1 to i − 1 as
they do not have high enough priority. Consequently, any feasible path Qi for demand i must include all
unit capacity edges of row i. Similarly, Q j must contain all of row j. Row j cuts off si from the sink t, so
Qi must meet Q j on row j. Demand i cannot use an edge in row j as demand j is already using up all the
capacity along that row. Thus Qi crosses Q j at the point they meet. As above, this meeting cannot occur
in columns 1 to i − 1. Thus the crossing point must occur on some column between i and j − 1.

Repeating our previous arguments, we obtain the following hardness result for priority flows. (Again,
it applies to both throughput and cardinality objectives as they coincide for priority flows.)
Corollary 1.4. The maximum single-sink priority flow problem cannot be approximated to within a factor
of m1/2−ε , for any ε > 0, in planar directed or undirected graphs.
We close the section by establishing Theorem 1.8. Consider a grid instance built from a YES instance
of the 2 disjoint path problem. As before we may find a routing of all demands with congestion at most 1.
Otherwise, suppose that the grid graph is built from a NO instance and consider a tree T returned by a
strong congestion algorithm. As it is a strong algorithm, the demand in row i must follow its canonical
path horizontally to the right as far as it can. As it is a confluent flow, all demands from rows > i must
accumulate at this rightmost node in row i. Inductively this implies that the total load at the rightmost node
in row 1 has load > N. As before, for any ε > 0 we may choose N sufficiently large so that N ≥ n1/2−ε .
Hence we have a YES instance of 2 disjoint paths if and only if the output from a n1/2−ε -approximate
strong congestion algorithm returns a solution with congestion ≤ N.

4 Logarithmic hardness of single-sink confluent flow with the no-bottle-
neck assumption
We now prove the logarithmic hardness of the confluent flow problem given the no-bottleneck assumption.
A similar two-step plan is used as for Theorem 1.3 but the analysis is more involved.
Step (1). We introduce a planar graph GN which has the same structure as our previous half-grid,
except its capacities are changed. As before, we have demands associated with the si ’s, but we assume
these demands are tiny—this guarantees that the no-bottleneck assumption holds. We thus refer to the
demands located at an si as the packets from si . We define GN to ensure that there is a collection of
pairwise crossing paths that can route packets of total value equal to the harmonic number ηN ≈ log N.

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 11
F. B RUCE S HEPHERD AND A DRIAN R. V ETTA

Step (2). We then build a new network G by replacing each node of GN by an instance of the 2-disjoint
paths problem. Again, this routing problem is chosen because it induces the following properties. If
it is a YES-instance, then we can find a routing that corresponds to pairwise crossing paths with the
correct capacities. Hence, we are able to route ηN demand. In contrast, if it is a NO-instance, the capacity
constraints within the gadgets become restrictive and force the maximum confluent flow value to be at
most 2.
It follows that an approximation algorithm with guarantee better than logarithmic would allow us to
distinguish between YES- and NO-instances of our routing problem, giving a lower bound of Ω(log N).
We will see that this bound is equal to Θ(log1−ε n).

4.1 An updated half-grid graph
Again we take the graph GN with N rows (now numbered from bottom to top) and N columns (now
numbered from right to left). As we are considering the confluent flow problem, we sub-divide the edges
in order to place capacities on the nodes. The nodes in the ith row and the nodes in the ith column have
capacity 1/i. The ith row extends as far as the ith column and vice versa; thus, we obtain a half-grid similar
to our earlier construction but with updated capacities. Then we add a sink t. There is an edge to t from
the bottom node (called ti ) in column i; the capacity of ti is 1/i. Finally, at the leftmost node (called si ) in
row i there is a collection of packets (“subdemands”) whose total weight is 1/i. These packets are very
small. In particular, they are much smaller than 1/n, so they satisfy the no-bottleneck assumption. The
construction is shown in Figure 4. In the directed setting, edges are oriented to the right and downwards.

sN 1/N 1/N

1/N
1/(N-1) 1/(N-1) 1/(N-1)
sN-1

1/N 1/(N-1)
1/(N-2) 1/(N-2) 1/(N-2) 1/(N-2)
sN-2

1/N 1/(N-1) 1/(N-2)

1/2 1/2 1/2 1/2 1/2
s2

1/N 1/(N-1) 1/(N-2) 1/2
1 1 1 1 1 1
s1

1/N 1/(N-1) 1/(N-2) 1/2 1

tN tN-1 tN-2 t2 t1

Figure 4: An Updated NBA Half-Grid GN .

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 12
I NAPPROXIMABILITY OF U NSPLITTABLE , P RIORITY AND C ONFLUENT F LOW

Again, there is a unique si -t path Pi∗ consisting only of nodes of weight 1/i, that is, the hooked path
that goes from si along the ith row and then down the ith column to t. Moreover, for i 6= j, the path Pi∗
intersects Pj∗ precisely once. If we route packets along the paths P∗ = {P1∗ , P2∗ , . . . , PN∗ }, then we obtain a
flow of total value ηN = 1 + (1/2) + · · · + (1/N). Since every node incident to t is used in P∗ with its
maximum capacity, this solution is a maximum single-sink flow.
For the hardness construction, we again build a new instance G by replacing each degree 4 node in GN
with an instance of the 2-disjoint paths problem. For this confluent flow problem, our gadgets correspond
to the capacitated node-disjoint paths problem.4 We replace the node at the intersection of row i and
column j (with i < j) in GN by a copy of the routing graph H—see Section 2. For clarity, we denote the
gadget H located at this intersection by Hi, j . The nodes x1 and y1 are placed on row i and have (high)
capacity ci = 1/i. The nodes x2 and y2 are placed on column j and have (low) capacity c j = 1/ j. We
also let α = ci and β = c j .
If H is a YES instance, then we can find a high capacity path, Q1 , from x1 to y1 and a low capacity
path (that is, a path that may use both high and low capacity edges), Q2 , from x2 to y2 that is node disjoint
from Q1 . Clearly, combining the hooked paths P∗ = {P1∗ , P2∗ , . . . , PN∗ } with the paths Q1 and Q2 within
each gadget gives a confluent flow of value ηN .

si+1

wj wi+2 wi+1
wj+1 zi
si
zj zi+2 zi+1

si-1

Figure 5: The Interval I[i, j] of Gadgets.

Now, let’s examine what happens if H is a NO instance. We require the following terminol-
ogy. Let I[i, j] = {Hi, j , Hi, j−1 , . . . , Hi,i+2 , Hi,i+1 } be an interval of gadgets in row i. We say that
{z j , z j−1 , . . . , zi+1 , zi } are the exit nodes for this interval of gadgets, where zi is the “y1 node” in gadget
Hi,i+1 and zk , for j ≥ k ≥ i + 1 is the y2 node in gadget Hi,k . We say that {w j+1 , w j , . . . , wi+1 } are the
entry nodes for this interval of gadgets, where w j+1 is the x1 node in gadget Hi, j and wk , for j ≥ k ≥ i + 1,
is the x2 node in gadget Hi,k . (We remark that, in the undirected case, flow may actually enter a gadget
4 In the directed case, we could simply adopt the uncapacitated version but its easier to keep the capacitated version in mind

for both cases.

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 13
F. B RUCE S HEPHERD AND A DRIAN R. V ETTA

through an “exit" node and leave via an “entry" node.) This is illustrated in Figure 5 where the entry
nodes to I[i, j] are shown in blue and the exit nodes in red.
The next lemma bounds the amount of confluent flow which can be sent from {si , si+1 , . . . , sN }
through I[i, j] (via its entry nodes) and on to its exit nodes. Formally, we refer to an I[i, j] confluent flow
as any confluent flow where

(i) the source of any flow path is in {si , si+1 , . . . , sN },

(ii) the terminal node of any flow path is an exit node of I[i, j] and each flow path contains precisely
one such exit node,5 and

(iii) the edge entering the exit node of any flow path is inside one of the gadgets from I[i, j].

Lemma 4.1. Let H be a NO instance and let I[i, j] = {Hi, j , Hi, j−1 , . . . , Hi,i+1 } be an interval of gadgets
for a pair i, j, where i < j ≤ N. Then the value of any I[i, j] confluent flow is at most 2 · ( j − i + 1)/ j.

Before proceeding to the proof, note that any confluent flow in the whole instance corresponds to
an I[1, n] confluent flow. This is because any flow from {s1 , s2 , . . . , sN } to t must reach the exit nodes of
I[1, n] from within I[1, n] and not from below. Hence the following key property is immediate.

Corollary 4.2. If H is a NO instance, then the maximum value of a confluent flow in GN is at most 2.

Proof. We now prove Lemma 4.1 by induction on decreasing values of i, and then increasing values
of j. For the base case consider i = N − 1. Now j can take only the value N. The interval I[N − 1, N]
consists of a single gadget, namely Hn−1,n and so all flow from sN and sN−1 must pass through this
gadget. We now show that the maximum amount of flow that can be sent confluently from sN and
sN−1 to the exits {zN−1 , zN } is ( j − i + 1/ j) = (N − (N − 1) + 1)(N) = (2/N). Clearly this is less than
2 · ( j − i + 1/ j) = (4/N). We have four cases, as illustrated in Figure 6.

(i) The flows through x1 and x2 meet and merge and exit through y1 = zN−1 . As y1 has capacity
1/(N − 1), the total flow is at most 1/(N − 1) < (2/N).

(ii) The flows through x1 and x2 meet and merge and then exit through y2 = zN . As y2 has capacity
1/N, the total flow is at most 1/N < 2/N.

(iii) Using two node-disjoint paths, the flow through x1 exits at y2 = zN and the flow through x2 exits at
y1 = zN−1 . Since the capacities into x2 and out of y2 are 1/N, the total flow is at most 2/N.

(iv) Using two node-disjoint paths, the flow through x1 exits at y1 = zN−1 and the flow through x2 exits
at y2 = zN . But, H is a NO instance. Therefore, the path used from x1 to y1 must use at least one
low capacity node. Thus, again, the flow value is at most 2/N, as required.

We proceed by induction. Take a pair i, j with i < j ≤ N. If j = i + 1 then I[i, j] consists of a single
gadget and the argument used in the base case can be successfully applied. So assume that j > i + 1.
Now take any confluent flow from {si , si+1 , . . . , sN } through I[i, j] (via its entry nodes) to its exit nodes.
5 Note however that a flow path may actually contain multiple entry nodes of I[i, j].

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 14
I NAPPROXIMABILITY OF U NSPLITTABLE , P RIORITY AND C ONFLUENT F LOW

1/N 1/N
sN sN
1/N 1/N
x2 x2
H H
x1 y1 = zN-1 x1 y1 = zN-1
sN-1 sN-1
1/(N-1) 1/(N-1) 1/(N-1) 1/(N-1)

y2 = zN y2 = zN
(i) 1/N 1/(N-1) (ii) 1/N 1/(N-1)

1/N 1/N
sN sN
1/N 1/N
x2 x2
H H
x1 y1 = zN-1 x1 y1 = zN-1
sN-1 sN-1
1/(N-1) 1/(N-1) 1/(N-1) 1/(N-1)

y2 = zN y2 = zN
(iii) 1/N 1/(N-1) (iv) 1/N 1/(N-1)

Figure 6: Base Case.

Observe that this flow can reach the entry nodes of I[i, j] in two ways. Either it reaches the entry node
w j+1 via the horizontal edge e in row i or it reaches the entry nodes {w j , w j−1 , . . . , wi+1 } from above via
the entry (and exit) nodes of the interval I[i + 1, j]. See Figure 7. (Recall we are not interested in flow
that reaches the exit nodes of I[i, j] from below, as this flow does not pass through I[i, j].)
Now suppose no flow is sent to exit node z j . Since, j > i + 1, by induction on the case {i, j − 1}, the
total flow sent is at most

2 · (( j − 1) − i + 1)/( j − 1) = 2 · ( j − i)/( j − 1) ≤ 2 · ( j − i + 1)/ j

as required. So we now assume that some flow is sent to exit node z j .
We consider two types of flow: (Type 1) flow that does not enter at w j+1 and (Type 2) flow that
does enter at w j+1 . Let us first consider the Type 1 flow. Some of this flow may originate from
{si+1 , si+2 , . . . , sN } and hence forms an I[i + 1, j] confluent flow. By induction, the value of this type of
flow is at most 2 · ( j − (i + 1) + 1)/ j = 2 · ( j − i)/ j. The rest of the Type 1 flow originates at si . Because
the flow is confluent these packets route along a single path. Since this flow path does not enter w j+1 , it
must go via an entry node of I[i + 1, j]. But to reach I[i + 1, j], without touching any exit nodes of I[i, j],
this path must traverse up some column ` where N ≥ ` > j. The capacity of the nodes in this column are
1/` < 1/ j. Consequently this class of Type 1 flow contributes flow value at most 1/ j.
So let us now consider Type 2 flow. This flow originates either at {si+1 , si+2 , . . . , sN } or {si } and
travels through the horizontal edge e in row i into gadget Hi, j at node w j+1 . Suppose first that this flow
either goes down through exit z j or up through entry w j in gadget Hi, j . Then this flow contributes value at
most 1/ j, because both these nodes have capacity 1/ j. Otherwise this flow exits gadget Hi, j on the right
via its y1 node. Recall, by assumption, some other flow does reach z j . By confluence, this flow cannot

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 15
F. B RUCE S HEPHERD AND A DRIAN R. V ETTA

si+2

si+1

wj wi+2 wi+1
wj+1 zi
si
e
zj zi+2 zi+1

Figure 7: Induction Step.

have entered the gadget via w j+1 or the y1 node. Hence it must come via the x2 = w j node. Thus we have
disjoint paths from x1 to y1 and from x2 to y2 . Because H is a NO instance, the path from x1 to y1 , used
by the Type 2 flow, must contain an edge of low capacity. Thus the Type 2 flow path again contributes at
most value 1/ j. So total flow is at most

2 · ( j − i)/ j + (1/ j) + (1/ j) = 2 · ( j − i + 1)/ j

as desired. The result follows by induction.

We can now establish the claimed inapproximability bound.
Theorem 1.7. Given the no-bottleneck assumption, the single-sink confluent flow problem cannot be
approximated to within a factor O(log1−ε n), for any ε > 0, unless P = NP. This holds for both the
maximum cardinality and maximum throughput objectives in undirected and directed graphs.

Proof. It follows that if we could approximate the maximum confluent flow problem in G to a factor
better than ηN /2, we could determine whether the optimal solution is 2 or ηN . This in turn would allow
us to determine whether H is a YES- or a NO-instance.
Note that G has n = Θ(pN 2 ) edges, where p = |V (H)|. If we take N = Θ(p(1/2)((1/ε)−1) ), where ε > 0
is a small constant, then ηN = Θ((1/2)((1/ε) − 1) log p). For p sufficiently large, this is Ω((log n)1−ε ) =
((1/ε) log p)1−ε . This gives a lower bound of Ω((log n)1−ε ).

5 Stronger lower bounds for cardinality single-sink unsplittable flow with
arbitrary demands
In the large-demand regime even stronger lower bounds can be achieved for the cardinality objective.
To see this, we explain the technique of Azar and Regev [3] (used to prove Theorem 1.1) in Section 5.1

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 16
I NAPPROXIMABILITY OF U NSPLITTABLE , P RIORITY AND C ONFLUENT F LOW

and show how to extend it to undirected graphs and to confluent flows. Then in Section 5.2, we combine
their construction with the half-grid graph to obtain lower bounds in terms of the bottleneck value
(Theorem 1.5).

5.1 m1−ε hardness in the large-demand regime
Theorem 1.2. If P 6= NP then, for any ε > 0, there is no O(m1−ε )-approximation algorithm for the
cardinality objective of the single-sink unsplittable/confluent flow problem in undirected graphs.

Proof. We begin by describing the construction of Azar and Regev for directed graphs. They embed
instances of the uncapacitated 2-disjoint paths problem into a directed path. Formally, we start with a
directed path z1 , z2 , . . . , z` where t = z` forms our sink destination for all demands. In addition, for each
i < `, there are two parallel edges from zi−1 to zi . One of these has capacity 2i and the other has a smaller
capacity of 2i − 1. There is a demand si from each zi , i < ` to z` of size 2i+1 . Note that this unsplittable
flow instance is feasible as follows. For each demand s j , we may follow the high capacity edge from z j
to z j+1 (using up all of its capacity) and then use low capacity edges on the path z j+1 , z j+2 , . . . , z` . Call
these the canonical paths for the demands. The total demand on the low capacity edge from z j is then
∑i≤ j 2i = 2 j+1 − 1, as desired.
Now replace each node z j , 1 ≤ j < `, by an instance H j of the uncapacitated directed 2-disjoint paths
problem. Each edge in H j is given capacity 2 j+1 . Furthermore we have the following.

(i) The tail of the high capacity edge out of z j is identified with the node y2 .

(ii) The tail of the low capacity edge out of z j is identified with y1 .

(iii) The heads of both edges into z j (if they exist) are identified with x1 .

(iv) The node x2 becomes the starting point of the demand s j from z j .

This construction is shown in Figure 8.

s1
s2
s3
sq-‐1
sq

x2
x2
x2
23-‐1
2q-‐2-‐1
x2
x2
t
21-‐1
22-‐1
y1
2 -‐1
q
y1
2 -‐1
q-‐1
s0
x1
y1
x1
y1
x1
y1
x1
x1
y2
y2
y2
y2
y2

22
23
2q-‐2
2q-‐1
2q
21

Figure 8: An Azar-Regev Path.

Now if we have a YES-instance of the 2-disjoint paths problem, we may then simulate the canonical
paths in the standard way. The demand in H j uses the directed path from x2 to y2 in H j ; it then follows the
high capacity edge from y2 to the x1 -node in the next instance H j+1 . All the total demand arriving from

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 17
F. B RUCE S HEPHERD AND A DRIAN R. V ETTA

upstream H i ’s entered H j at its node x1 and follows the directed path from x1 to y1 . This total demand is
at most ∑i≤ j 2i and thus fits into the low capacity edge from H j into H j+1 . Observe that this routing is
also confluent in our modified instance because the paths in the H j ’s are node-disjoint. Hence, if we have
a YES-instance of the 2-disjoint paths problem, both the unsplittable and confluent flow problems have a
solution routing all of the demands.
Now suppose that we have a NO-instance, and consider a solution to the unsplittable (or confluent)
flow problem. Take the highest value i such that the demand from H i is routed. By construction, this
demand must use a path P2 from x2 to y2 . But this saturates the high capacity edge from y2 . Hence any
demand from H j , j < i must pass from y1 to x1 while avoiding the edges of P2 . This is impossible, and so
we route at most one demand.
This gives a gap of ` for the cardinality objective. Azar-Regev then choose ` = |V (H)|d1/εe to obtain
0
a hardness of Ω(n1−ε ).
Now consider undirected graphs. Here we use an undirected instance of the capacitated 2-disjoint
paths problem. We plug this instance into each H j , and use the two capacity values of β = 2 j+1 and
α = 2 j+1 − 1. A similar routing argument then gives the lower bound.

We remark that it is easy to see why this approach does not succeed for the throughput objective. The
use of exponentially growing demands implies that high throughput is achieved simply by routing the
largest demand.

5.2 Lower bounds for arbitrary demands
By combining paths and half-grids we are able to refine the lower bounds in terms of the bottleneck value
(or demand spread).
Theorem 1.5. Consider any fixed ε > 0 and dmax /umin > 1. Itpis NP-hard to approximate cardinality
single-sink unsplittable/confluent flow to within a factor of O( log(dmax /umin ) · m1/2−ε ) in undirected
or directed graphs. For unsplittable flow, this remains true for planar graphs.

Proof. We start with two parameters p and q. We create p copies of the Azar-Regev path and attach them
to a p × p half-grid, as shown in Figure 9.
Now take the ith Azar-Regev path, for each i = 1, 2 . . . p. The path contains q supply nodes with
demands of sizes 2(i−1)q , 2(i−1)q+1 , . . . , 2iq−1 . (Supply node s j has demand 2 j−1 .) Therefore the total
demand on path i is τi := 2(i−1)q (2q − 1) < 2iq . The key point is that the total demand of path i is less
than the smallest demand in path i + 1. Note that we have pq demands, and thus demand sizes from 20
up to 2 pq−1 . Consequently the demand spread is 2 pq−1 . We set umin = dmin and thus

pq − 1 = log (dmax /dmin ) = log (dmax /umin ) .

It remains to prescribe capacities to the edges of the half-grid. To do this every edge in ith canonical
hooked path has capacity τi (not ci ). These capacity assignments, in turn, induce corresponding capacities
in each of the disjoint paths gadgets. It follows that if each gadget on the paths and half-grid correspond
to a YES-instance gadget then we may route all pq demands.
Now suppose the gadgets correspond to a NO-instance. It follows that we may route at most one
demand along each Azar-Regev path. But, by our choice of demand values, any demand on the ith path

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 18
I NAPPROXIMABILITY OF U NSPLITTABLE , P RIORITY AND C ONFLUENT F LOW

s2 s3 sq‐1 sq
s1

spq‐1 spq
s(p‐1)q+1 s(p‐1)q+2

t1 t2 t3 tp‐1 tp

Figure 9:

is too large to fit into any column j < i in the half-grid. Hence we have the same conditions required
in Theorem 1.3 to show that at most one demand in total can feasibly route. It follows that we cannot
approximate the cardinality objective to better than a factor pq.
Note that the construction contains at most m = O((qp + p2 ) · |E(H)|) edges, where H is the size of
the 2-disjoint paths instance. Now we select p and q such that q ≥ p and pq ≥ |E(H)|1/ε . Then, for some
constant C, we have
p p
C · m1/2−ε · log(dmax /dmin ) = m1/2−ε · log(dmax /dmin )
√ √
≤ pq · pq
= pq .

Therefore, since we cannot
p approximate to within pq, we cannot approximate the cardinality objective to
better than a factor O( log(dmax /umin ) · m1/2−ε ).

6 Upper bounds for flows with arbitrary demands
In this section we present upper bounds for maximum flow problems with arbitrary demands.

6.1 Unsplittable flow with arbitrary demands
One natural approach for the cardinality unsplittable flow problem is used repeatedly in the literature
(even for general multiflows) and we appeal to it in the proof of Theorem 1.6 and defer the details for
now. Group the demands into at most O(log dmax /dmin ) bins, and then consider each bin separately.
This approach can also be applied to the throughput objective or the more general profit-maximisation

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 19
F. B RUCE S HEPHERD AND A DRIAN R. V ETTA

model. This immediately incurs, however, a loss factor relating to the number of bins, and this feels
slightly artificial. In fact, given the NBA regime, there is no need to lose this extra factor; Baveja et
√
al. [4] gave an O( m) approximation for profit-maximisation when dmax ≤ umin . On the other hand, our
lower bound in Theorem 1.5 shows that if dmax > umin we do need to lose some factor dependent on dmax .
√
But how large does this need to be? The current best upper bound is O(log(dmax /umin ) · m log m) by
Guruswami et al. [21], and this works for the general profit-maximisation model.6 For the cardinality
and throughput objectives, however, we can obtain a better upper bound. The proof combines analyses
from [4] and [25] (which focus on the NBA case). We emphasize that the following theorem applies to all
multiflow problems not just the single-sink case.
We also point out a related analysis of the greedy algorithm for unsplittable flows (without NBA) given
√
by Kolman [26]. In the cardinality maximization version he gives a O(min{n2/3 , m})-approximation
√
which is superior to our bound below. In the directed setting, he obtains a O(min{n4/5 , m})-approxi-
mation for cardinality maximization (Theorem 6 of [26]).
√
Theorem 1.6. There is an O( m log(dmax /umin )) approximation algorithm for cardinality unsplittable
√
flow and an O( m log n) approximation algorithm for throughput unsplittable flow, in both directed and
√
undirected graphs. There is an O(log(dmax /umin ) m log m) approximation for general weights.

Proof. We apply a result from [21] which shows that for cardinality unsplittable flow, with dmax ≤ ∆dmin ,
√
the greedy algorithm yields a O(∆ m) approximation. Their proof is a technical extension of the
greedy analysis of Kolliopoulos and Stein [25]. We first find an approximation for the sub-instance
√
consisting of the demands at most umin . This satisfies the NBA and an O( m)-approximation is known
for general profits [4]. More precisely, we define bin i to be the demands whose value lies in the range
(2i umin , 2i+1 umin ], but for bin 0 we also include demands of value exactly umin . Thus we need at most
log(dmax /umin ) ≤ log(dmax /dmin ) bins. The greedy algorithm above then gives the desired guarantee for
the cardinality problem. The same approach applies for the throughput objective, since all demands within
the same bin have values within a constant factor of each other. Moreover, we require only log n bins as
demands of at most dmax /n may be discarded as they are not necessary for obtaining high throughput.

As alluded to earlier, this upper bound is not completely satisfactory as pointed out in [8]. Namely,
all of the lower bound instances have a linear number of edges m = O(n). Therefore, it is possible that
√
there exist upper bounds dependent on n. Indeed, for the special case of MEDP in undirected graphs
√
and directed acyclic graphs O( n)-approximations have been developed [9, 28].

6.2 Priority flow with arbitrary demands
Next we show that the lower bound for the maximum priority flow problem is tight.

Theorem 6.1. Consider an instance of the maximum priority flow problem with k priority classes. There
√
is a polytime algorithm that approximates the maximum flow to within a factor of O(min{k, m}).
6 Actually, they state the bound as log3/2 m because exponential-size demands are not considered in that paper.

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 20
I NAPPROXIMABILITY OF U NSPLITTABLE , P RIORITY AND C ONFLUENT F LOW

√
Proof. First suppose that k ≤ m. Then for each class i, we may find the optimal priority flow by solving
a maximum flow problem in the subgraph induced by all edges of priority i or better. This yields a
√
k-approximation. Next consider the case where m < k. Then we may apply Lemma 6.2, below, which
√
implies that the greedy algorithm yields a O( m)-approximation. The theorem follows.

The following proof for uncapacitated networks follows ideas from the greedy analysis of Klein-
√
berg [23], and Kolliopoulos and Stein [25]. One may also design an O( m)-approximation for general
edge capacities using more intricate ideas from [21]; we omit the details.
√
Lemma 6.2. A greedy algorithm yields a O( m)-approximation to the maximum priority flow problem.
Proof. We now run the greedy algorithm as follows. On each iteration, we find the demand si which
has a shortest feasible path in the residual graph. Let Pi be the associated path, and delete its edges. Let
the greedy solution have cardinality t. Let O be the optimal maximum priority flow and let Q be those
demands which are satisfied in some optimal solution but not by the greedy algorithm. We aim to give an
upper bound on the size of Q.
Let Q be a path used in the optimal solution satisfying some demand in Q. Consider any edge e and
the greedy path using it. We say that Pi blocks an optimal path Q if i is the least index such that Pi and Q
share a common edge e. Clearly such an i exists or else we could still route on Q.
Let li denote the length of Pi . Let ki denote the number of optimal paths (corresponding to demands
in Q) that are blocked by Pi . It follows that ki ≤ li . But, by the definition of the greedy algorithm, we
have that each such blocked path must have length at least li at the time when Pi was packed. Hence it
used up at least li ≥ ki units of capacity in the optimal solution. Therefore the total capacity used by the
unsatisfied demands from the optimal solution is at least ∑ti=1 ki2 . As the total capacity is at most m we
obtain

(∑ti=1 ki )2 t
≤ ∑ ki2 ≤ m (6.1)
t i=1

where the first inequality is by the Chebyshev Sum Inequality or simply convexity. Since ∑i ki = |Q| =
√
|O| − t, we obtain (|O| − t)2 /t ≤ m. One may verify that if t < |O|/ m then this inequality implies
√
|O| = O( m) and, so, routing a single demand yields the desired approximation.

7 Conclusion
√ √
It would be interesting to improve the upper bound in Theorem 1.6 to be in terms of n rather than m.
√ 2/3
p in the case of general directed MEDP where the best upper bound is min{ m, n }.
This is already open
Eliminating the log(m) term from Theorem p 1.6 in the general profit maximization, and resolving the
discrepancy with Theorem 1.5 (between log(dmax /umin ) and log(dmax /umin )) would also round out the
picture.

Acknowledgments. We are grateful to the referees for their excellent reports which contained many
detailed comments which greatly improved the paper. We also thank Qin Bo, Mordecai Golin, Petr
Kolman and Guyslain Naves for their careful reading and helpful comments. In particular, we are indebted

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 21
F. B RUCE S HEPHERD AND A DRIAN R. V ETTA

to Qin Bo and Mordecai Golin for detecting a flaw in the proof for the undirected case of Theorem 1.7 in
an earlier version of this paper. Finally, the authors gratefully acknowledge support from the NSERC
Discovery Grant Program.

References
[1] M ATTHEW A NDREWS , J ULIA C HUZHOY, V ENKATESAN G URUSWAMI , S ANJEEV K HANNA ,
K UNAL TALWAR , AND L ISA Z HANG: Inapproximability of edge-disjoint paths and low congestion
routing on undirected graphs. Combinatorica, 30(5):485–520, 2010. [doi:10.1007/s00493-010-
2455-9] 4
[2] M ATTHEW A NDREWS AND L ISA Z HANG: Logarithmic hardness of the undirected edge-
disjoint paths problem. J. ACM, 53(5):745–761, 2006. Preliminary version in STOC’05.
[doi:10.1145/1183907.1183910] 4
[3] YOSSI A ZAR AND O DED R EGEV: Combinatorial algorithms for the unsplittable flow problem.
Algorithmica, 44(1):49–66, 2006. Preliminary version in IPCO’01. [doi:10.1007/s00453-005-1172-
z] 3, 5, 16
[4] A LOK BAVEJA AND A RAVIND S RINIVASAN: Approximation algorithms for disjoint paths
and related routing and packing problems. Math. Oper. Res., 25(2):255–280, 2000.
[doi:10.1287/moor.25.2.255.12228] 20
[5] PAUL S. B ONSMA , J ENS S CHULZ , AND A NDREA W IESE: A constant-factor approximation
algorithm for unsplittable flow on paths. SIAM J. Computing, 43(2):767–799, 2014. Preliminary
version in FOCS’11. [doi:10.1137/120868360, arXiv:1102.3643] 3
[6] M OSES C HARIKAR , J OSEPH S. NAOR , AND BARUCH S CHIEBER: Resource optimization in QoS
multicast routing of real-time multimedia. IEEE/ACM Transactions on Networking, 12(2):340–348,
2004. Preliminary version in INFOCOM’00. [doi:10.1109/TNET.2004.826288] 4
[7] C HANDRA C HEKURI , A LINA E NE , AND N ITISH KORULA: Unsplittable flow in paths and trees and
column-restricted packing integer programs. In Proc. 12th Internat. Workshop on Approximation
Algorithms for Combinatorial Optimization Problems (APPROX’09), pp. 42–55. Springer, 2009.
[doi:10.1007/978-3-642-03685-9_4] 3
[8] C HANDRA C HEKURI AND S ANJEEV K HANNA: Edge-disjoint paths revisited. ACM Trans. Algo-
rithms, 3(4), 2007. Preliminary version in SODA’03. [doi:10.1145/1290672.1290683] 20
√
[9] C HANDRA C HEKURI , S ANJEEV K HANNA , AND F. B RUCE S HEPHERD: An O( n) approximation
and integrality gap for disjoint paths and unsplittable flow. Theory of Computing, 2(7):137–146,
2006. [doi:10.4086/toc.2006.v002a007] 20
[10] C HANDRA C HEKURI , S ANJEEV K HANNA , AND F. B RUCE S HEPHERD: Edge-disjoint paths in
planar graphs with constant congestion. SIAM J. Computing, 39(1):281–301, 2009. Preliminary
version in STOC’06. [doi:10.1137/060674442] 5

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 22
I NAPPROXIMABILITY OF U NSPLITTABLE , P RIORITY AND C ONFLUENT F LOW

[11] J IANGZHUO C HEN , ROBERT D. K LEINBERG , L ÁSZLÓ L OVÁSZ , R AJMOHAN R AJARAMAN ,
R AVI S UNDARAM , AND A DRIAN R. V ETTA: (Almost) Tight bounds and existence theorems for
single-commodity confluent flows. J. ACM, 54(4):16, 2007. Preliminary version in STOC’04.
[doi:10.1145/1255443.1255444] 3

[12] J IANGZHUO C HEN , R AJMOHAN R AJARAMAN , AND R AVI S UNDARAM: Meet and merge: Approx-
imation algorithms for confluent flows. J. Comput. System Sci., 72(3):468–489, 2006. Preliminary
version in STOC’03. [doi:10.1016/j.jcss.2005.09.009] 2, 3

[13] J ULIA C HUZHOY: Routing in undirected graphs with constant congestion. SIAM J. Com-
puting, 45(4):1490–1532, 2016. Preliminary version in STOC’12. [doi:10.1137/130910464,
arXiv:1107.2554] 4

[14] J ULIA C HUZHOY, A NUPAM G UPTA , J OSEPH S. NAOR , AND A MITABH S INHA: On the approxima-
bility of some network design problems. ACM Trans. Algorithms, 4(2):23:1–17, 2008. Preliminary
version in SODA’05. [doi:10.1145/1361192.1361200] 4

[15] J ULIA C HUZHOY AND S HI L I: A polylogarithmic approximation algorithm for edge-disjoint
paths with congestion 2. J. ACM, 63(5):45:1–51, 2016. Preliminary version in FOCS’12.
[doi:10.1145/2893472, arXiv:1208.1272] 4

[16] S TEVEN C OSARES AND I RAJ S ANIEE: An optimization problem related to balancing loads on
SONET rings. Telecommunication Systems, 3(2):165–181, 1994. [doi:10.1007/BF02110141] 2, 3

[17] Y EFIM D INITZ , NAVEEN G ARG , AND M ICHEL X. G OEMANS: On the single-source unsplit-
table flow problem. Combinatorica, 19(1):17–41, 1999. Preliminary version in FOCS’98.
[doi:10.1007/s004930050043] 3

[18] PATRICK D ONOVAN , F. B RUCE S HEPHERD , A DRIAN R. V ETTA , AND G ORDON W ILFONG:
Degree-constrained network flows. In Proc. 39th STOC, pp. 681–688. ACM Press, 2007.
[doi:10.1145/1250790.1250889] 3

[19] DANIEL D RESSLER AND M ARTIN S TREHLER: Capacitated confluent flows: complexity and
algorithms. In Proc. 7th Internat. Conf. on Algorithms and Complexity (CIAC’10), pp. 347–358.
Springer, 2010. [doi:10.1007/978-3-642-13073-1_31] 3

[20] S TEVEN F ORTUNE , J OHN H OPCROFT, AND JAMES W YLLIE: The directed subgraph homeomor-
phism problem. Theor. Comput. Sci., 10(2):111–121, 1980. [doi:10.1016/0304-3975(80)90009-2]
7

[21] V ENKATESAN G URUSWAMI , S ANJEEV K HANNA , R AJMOHAN R AJARAMAN , F. B RUCE S HEP -
HERD , AND M IHALIS YANNAKAKIS: Near-optimal hardness results and approximation algorithms
for edge-disjoint paths and related problems. J. Comput. System Sci., 67(3):473–496, 2003. Prelimi-
nary version in STOC’99. [doi:10.1016/S0022-0000(03)00066-7] 3, 4, 7, 8, 9, 20, 21

[22] J ON M. K LEINBERG: Approximation Algorithms for Disjoint Paths Problems. Ph. D. thesis, MIT,
1996. Available from DSpace@MIT. 2

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 23
F. B RUCE S HEPHERD AND A DRIAN R. V ETTA

[23] J ON M. K LEINBERG: Single-source unsplittable flow. In Proc. 37th FOCS, pp. 68–77. IEEE Comp.
Soc. Press, 1996. [doi:10.1109/SFCS.1996.548465] 2, 3, 21

[24] J ON M. K LEINBERG AND É VA TARDOS: Approximations for the disjoint paths problem in high-
diameter planar networks. J. Comput. System Sci., 57(1):61–73, 1998. Preliminary version in
STOC’95. [doi:10.1006/jcss.1998.1579] 5

[25] S TAVROS G. KOLLIOPOULOS AND C LIFFORD S TEIN: Approximating disjoint-path problems using
packing integer programs. Math. Program., 99(1):63–87, 2004. Preliminary version in IPCO’98.
[doi:10.1007/s10107-002-0370-6] 20, 21

[26] P ETR KOLMAN: A note on the greedy algorithm for the unsplittable flow problem. Inform. Process.
Lett., 88(3):101–105, 2003. [doi:10.1016/S0020-0190(03)00351-X] 20

[27] G UYSLAIN NAVES , N ICOLAS S ONNERAT, AND A DRIAN R. V ETTA: Maximum flows on disjoint
paths. In Proc. 13th Internat. Workshop on Approximation Algorithms for Combinatorial Optimiza-
tion Problems (APPROX’10), pp. 326–337. Springer, 2010. [doi:10.1007/978-3-642-15369-3_25]
7

[28] T HÀNH N GUYEN: On the disjoint paths problem. Oper. Res. Lett., 35(1):10–16, 2007.
[doi:10.1016/j.orl.2006.02.001] 20

[29] N EIL ROBERTSON AND PAUL D. S EYMOUR: Graph minors. XIII. The disjoint paths problem. J.
Comb. Theory, Ser. B, 63(1):65–110, 1995. [doi:10.1006/jctb.1995.1006] 7

[30] L OÏC S EGUIN -C HARBONNEAU AND F. B RUCE S HEPHERD: Maximum edge-disjoint paths in
planar graphs with congestion 2. In Proc. 52nd FOCS, pp. 200–209. IEEE Comp. Soc. Press, 2011.
[doi:10.1109/FOCS.2011.30] 5

[31] F. B RUCE S HEPHERD: Single-sink multicommodity flow with side constraints. In Research Trends
in Combinatorial Optimization, pp. 429–450. Springer, 2009. [doi:10.1007/978-3-540-76796-1_20]
3

[32] F. B RUCE S HEPHERD , A DRIAN R. V ETTA , AND G ORDON W ILFONG: Polylogarithmic approxi-
mations for the capacitated single-sink confluent flow problem. In Proc. 56th FOCS, pp. 748–758.
IEEE Comp. Soc. Press, 2015. [doi:10.1109/FOCS.2015.51] 5

AUTHORS

F. Bruce Shepherd
Professor
McGill University, Montreal, Canada
bruce shepherd mcgill ca
http://www.mcgill.ca/~bshepherd

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 24
I NAPPROXIMABILITY OF U NSPLITTABLE , P RIORITY AND C ONFLUENT F LOW

Adrian R. Vetta
Associate professor
McGill University, Montreal, Canada
vetta math mcgill ca
http://www.mcgill.ca/~vetta

ABOUT THE AUTHORS

B RUCE S HEPHERD graduated from C&O at the University of Waterloo in 1990. His
advisor was Bill Pulleyblank. His thesis focused on packing problems and polyhedral
combinatorics. Apart from his passion for the theory of algorithms and optimization, he
has also endeavoured to apply the gospel in practice. He has worked as an operations
research consultant in London and worked for 10 years at Bell Labs, Lucent Technologies.

A DRIAN V ETTA is an Associate Professor in the Department of Mathematics & Statistics
and the School of Computer Science at McGill University. He holds a B. Sc. and M. Sc.
from the London School of Economics and a doctorate from MIT, written under the
supervision of Santosh Vempala.

T HEORY OF C OMPUTING, Volume 13 (20), 2017, pp. 1–25 25