Authors Henning Bruhn, Jakub {\v{C}}ern{\'y}, Alexander Hall, Petr Kolman, Ji{\v{r}}{\'\i} Sgall,
License CC-BY-ND-2.0
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20
http://theoryofcomputing.org
Single Source Multiroute Flows and Cuts on
Uniform Capacity Networks∗
Henning Bruhn Jakub Černý† Alexander Hall Petr Kolman‡
Jiřı́ Sgall§
Received: September 6, 2007; published: April 16, 2008.
Abstract: For an integer h ≥ 1, an elementary h-route flow is a flow along h edge disjoint
paths between a source and a sink, each path carrying a unit of flow, and a single commodity
h-route flow is a non-negative linear combination of elementary h-route flows. An instance
of a single source multicommodity flow problem for a graph G = (V, E) consists of a source
vertex s ∈ V and k sinks t1 , . . . ,tk ∈ V corresponding to k commodities; we denote it I =
(s;t1 , . . . ,tk ). In the single source multicommodity multiroute flow problem, we are given
an instance I = (s;t1 , . . . ,tk ) and an integer h ≥ 1, and the objective is to maximize the
∗ A preliminary version of this work appeared in Proceedings of the 18th ACM-SIAM Symposium on Discrete Algo-
rithms [9].
† Supported by project 1M0021620808 (ITI) of Ministry of Education of the Czech Republic.
‡ Supported by European Commission within the 6th Framework Programme under contract 001907 “Dynamically Evolv-
ing, Large Scale Information Systems” (DELIS) and by project 1M0021620808 (ITI) of Ministry of Education of the Czech
Republic.
§ Partially supported by Institutional Research Plan No. AV0Z10190503, grant 201/05/0124 of GA ČR, and grant
IAA1019401 of GA AV ČR.
ACM Classification: G.2.2, F.2.2
AMS Classification: 68R10, 05C38, 68W25 ,90C27
Key words and phrases: Graphs, multi-route flow, paths, multicommodity flow, connectivity, approxi-
mation algorithms
Authors retain copyright to their work and grant Theory of Computing unlimited rights
to publish the work electronically and in hard copy. Use of the work is permitted as
long as the author(s) and the journal are properly acknowledged. For the detailed
copyright statement, see http://theoryofcomputing.org/copyright.html.
c 2008 Henning Bruhn, Jakub Černý, Alexander Hall, Petr Kolman, and Jiřı́ Sgall DOI: 10.4086/toc.2008.v004a001
H. B RUHN , J. Č ERN Ý , A. H ALL , P. KOLMAN , AND J. S GALL
total amount of flow that is transferred from the source to the sinks so that the capacity
constraints are obeyed and, moreover, the flow of each commodity is an h-route flow.
We study the relation between classical and multiroute single source flows on undi-
rected networks with uniform capacities and we provide a tight bound. In particular, we
prove the following result. Given an instance I = (s;t1 , . . . ,tk ) such that each s − ti pair is
h-connected, the maximum classical flow between s and the ti is at most (2 − 2/h)-times
larger than the maximum h-route flow between s and the ti and this is the best possible
bound for h ≥ 2. This, as we show, is in contrast to the situation of general multicom-
modity (i. e., multiple sources or non-uniform capacities) multiroute flows that are up to
k(1 − 1/h)-times smaller than their classical counterparts.
Furthermore, we introduce and investigate duplex flows defined so that the capacity con-
straints on edges are applied independently for each direction. We show that for networks
with uniform capacities and for instances as above the maximum classical flow between s
and the ti is the same as the maximum h-route duplex flow between s and the ti . Moreover,
the total flow on each edge in the duplex flow can be restricted to (2 − 2/h)C, where C is
the capacity of each edge.
As a corollary, we establish a max-flow min-cut theorem for the single source multi-
commodity multiroute flow and cut. An h-disconnecting cut for I is a set of edges F ⊆ E
such that for each i, the maximum h-route flow between s and ti is zero. We show that the
maximum h-route flow is within 2h −2 of the minimum h-disconnecting cut, independently
of the number of commodities; we also describe a (2h − 2)-approximation algorithm for the
minimum h-disconnecting cut problem.
1 Flows, multiroute flows and cuts
A classical flow is (roughly) a non-negative linear combination of unit flows along paths (cf. [2]). Clas-
sical flow theory is not much interested in the number of the paths or in interactions among them. It is
plausible, for example, that there is an edge in the network that is used by every path of a given flow;
a failure of this single edge results in a loss of the entire flow. This property of the classical flow is
undesirable in some applications and motivated the definition of a multiroute flow. For a given integer
h ≥ 1, the multiroute flow (or an h-route flow) is a flow that is decomposable into a non-negative linear
combination of elementary h-route flows where an elementary h-route flow is a flow along h edge dis-
joint paths between the source and the sink, each path carrying a unit of flow [21]. Closely related to this
is the concept of h-balanced flows. A flow of size M between two vertices is h-balanced if the flow on
every edge is at most M/h. Clearly, every h-route flow is an h-balanced flow; the opposite (less obvious)
claim is also true: Every h-balanced (acyclic) flow is an h-route flow [1, 6, 21].
A necessary and sufficient condition for the existence of an h-route flow between two vertices is that
the vertices are h-connected. A corollary of the equivalence of h-route flows and h-balanced flows is
that on uniform capacity networks with an h-connected source s and sink t, every maximum s-t-flow
is an h-route flow. However, for multicommodity flows and h-route flows, this relation is no longer
valid. We investigate the relation between flows and h-route flows for a special case of multicommodity
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 2
S INGLE S OURCE M ULTIROUTE F LOWS AND C UTS
problems, namely for single source problems. An instance of a single source multicommodity flow
problem for a graph G = (V, E) consists of a source vertex s ∈ V and k sinks t1 , . . . ,tk ∈ V corresponding
to k commodities; we denote it I = (s;t1 , . . . ,tk ). A (single-source) multicommodity flow is an h-route
flow if the flow corresponding to each commodity is an h-route flow.
We show that for undirected networks with uniform capacities and for instances I = (s;t1 , . . . ,tk )
such that s and ti are h-connected, for each i = 1, . . . , k, the maximum classical flow between s and the
ti is at most 2 − 2/h times larger than the maximum h-route flow between s and the ti ; this bound is the
best possible for h ≥ 2. In particular, for h = 2 the ratio is 1, implying that by imposing the requirement
that the flow be a 2-route flow, we do not lose anything with respect to the size of the flow. Moreover, if
the uniform capacity of the edges is integral, then there always exists a half-integral h-route flow of size
at least half of the maximum classical flow.
Furthermore, we introduce and investigate duplex flows defined so that the capacity constraints on
edges are imposed independently for each direction, as if each undirected edge is replaced by two di-
rected edges in the opposite direction. To give an example, an edge with capacity 1 is able to carry a flow
of 1 in both direction simultaneously but it is not able to carry a flow of 1.5 in one direction even if the
other direction is not used. This is a natural model for network flows and as far as we know no specific
attention was given to it. For classical single commodity flow and single source multicommodity flow,
the sizes of the maximum non-duplex and duplex flows coincide since any classical flow can be modified
so that no edge is used in both directions. For h-route flows this simple transformation no longer works.
Nevertheless, we show that for networks with uniform capacities and for instances I = (s;t1 , . . . ,tk ) such
that s and ti are h-connected, for each i = 1, . . . , k, the maximum classical flow between s and the ti has
the same size as the maximum h-route duplex flow between s and the ti . Moreover, the total flow on
each edge in the duplex flow can be restricted to 2 − 2/h. Thus, our bound for duplex flows implies the
results for non-duplex flows described in the previous paragraph (except for the half-integrality).
Our results for single source flows are in sharp contrast with the situation of general (i. e., multiple
sources or non-uniform capacities) multiroute multicommodity flows: we describe an example with k
commodities where the maximum classical flow is k(1 − 1/h)-times larger than the maximum h-route
flow.
The other subject of the paper is cuts for h-route flows. For the classical flow, a cut is a subset of
edges whose removal disconnects the source and the sink (or every source-sink pair, in a case of the
multicommodity flow). Analogously, we define cuts for h-route flows. A subset F ⊆ E of edges is called
an h-disconnecting cut for an instance of the multicommodity flow if no source-sink pair is h-connected
in (V, E \ F). The h-disconnecting cuts correspond to integral solutions of a dual of a natural linear
programming formulation of the multiroute flow problem (see Section 1.2). We establish a max-flow
min-cut theorem for the single source multiroute flow and the minimum disconnecting cut problems on
networks with uniform capacities. In particular, we show that the max-flow for the problem is within
2h − 2 of the min-cut. As a corollary of this relation we get a (2h − 2)-approximation algorithm for the
h-disconnecting cut problem.
1.1 Related results
Kishimoto and Takeuchi [22] and later Aggarwal and Orlin [1] studied single commodity multiroute
flows (cf. [6, 15, 14]). They provided the characterization of h-route flows as h-balanced flows and also
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 3
H. B RUHN , J. Č ERN Ý , A. H ALL , P. KOLMAN , AND J. S GALL
proved a duality of multiroute flows and multiroute cuts (for different cuts than those considered in this
paper). Multiroute flows and integral variants of multiroute flows have applications in communication
and routing problems (e. g., [4, 5, 20, 12] and references therein).
Another direction of research focuses on flows under the restriction that each commodity is allowed
to use only a limited number of paths: the edge disjoint paths problem and the unsplittable flow problem
allow one path per commodity [8, 10, 11, 19, 23, 25, 27, 26, 34]; the h-splittable flow problem allows
at most h, not necessarily disjoint, paths per commodity [7, 24, 31, 30]; particular attention has been
given to single source unsplittable flow problems [13, 16, 25, 33]. Though there is a certain similarity
between the h-splittable flows and the h-route flows (in fact, they may even coincide for some instances),
there is also a substantial difference. Whereas the h-splittable flows may split, the h-route flows have the
obligation to split.
Relations between flows and cuts have been studied for over half a century. Menger [32] observed
that the maximum number of edge disjoint paths between a pair of vertices is equal to the size of the mini-
mum subset of edges whose removal disconnects the pair. Ford and Fulkerson [17] proved the celebrated
theorem about the duality of (single commodity) flows and cuts in networks. Though an exact duality
does not hold for multicommodity flows and cuts, there are several theorems establishing an approxi-
mate duality (with the gap of order log k) for different variants of the problem (Leighton and Rao [28],
Aumann and Rabani [3], Linial, London and Rabinovich [29], Garg, Vazirani and Yannakakis [18]).
1.2 Preliminaries
As indicated in the title, in this paper we deal with networks with uniform capacities. For simplicity
and without loss of generality we assume throughout the paper that every edge has capacity one. The
number of vertices is denoted n and the number of edges m; we allow parallel edges. The letter k
denotes the number of commodities and the letter h the number of routes in the elementary multiroute
flow. Several times we need the characterization of h-route flows as h-balanced flows that was first
proved by Kishimoto and Takeuchi.
Theorem 1.1 ([1, 6, 21]). A single commodity flow without cycles is h-balanced if and only if it is an
h-route flow.
For an instance I of the multicommodity flow problem, we use Fh (I) for the size of the maximum h-
route flow and Fh,k (I) for the size of the maximum h-route duplex flow for the instance I. As mentioned
in the introduction, for single source multicommodity flow, the sizes of the maximum non-duplex and
duplex flows coincide. Thus we have Fh (I) ≤ Fh,k (I) ≤ F1 (I).
For a given flow, an empty edge is an an edge unused by the flow. We will deal with minimum
cost flows several times. In such cases we consider the uniform cost function (i. e., cost(e) = 1, ∀e ∈
E). Recall that a single source classical flow can be viewed as a single commodity flow problem and
therefore there exists an integral maximum flow for every instance I; there also exists a minimum cost
maximum flow that is integral, and its cost is just the number of non-empty edges.
Consider a network G = (V, E). Let s1 , . . . , sk be k sources and t1 , . . . ,tk be k sinks of a multicom-
modity flow problem; we call the sources and sinks also terminals. Define Qi as the set of all elementary
h-route flows between si and ti and let Q = ki=1 Qi . As far as we know, no exact combinatorial algorithms
S
for computing the maximum multicommodity flow are known (not even for the 1-route flow). Thus, for
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 4
S INGLE S OURCE M ULTIROUTE F LOWS AND C UTS
completeness we provide a linear programming formulation of the maximum h-route flow problem (the
variable f (q) represents the size of the flow along the h-system q, that is, a flow of size f (q)/h along
each of the h paths of q):
max ∑ f (q) (1.1)
q∈Q
∑ f (q)/h ≤ 1 ∀e ∈ E
q∈Q:e∈q
f (q) ≥ 0 ∀q ∈ Q .
The dual program corresponds to the fractional relaxation of the the minimum h-disconnecting cut prob-
lem:
min h · ∑ x(e) (1.2)
e∈E
∑ x(e) ≥ 1 ∀q ∈ Q
e∈q
x(e) ≥ 0 ∀e ∈ E .
By setting integrality constraints on the variables x, we get an integer linear programming formulation
of the minimum h-disconnecting cut problem.
2 Relating flows and multiroute flows
In this section, we show that h-route flows are not much smaller than classical flows under certain
assumptions: single source, uniform capacity, and connectivity. We prove the following theorems for
non-duplex and duplex flows, respectively.
Theorem 2.1. Let G = (V, E) be an undirected graph and let I = (s;t1 , . . . ,tk ) be an instance of the
single source multicommodity flow problem such that for each i, s and ti are h-connected for a given
h ≥ 2. Then
F1 (I) ≤ (2 − 2/h) · Fh (I) . (2.1)
There also exists a half-integral h-route flow of size at least F1 (I)/2.
Theorem 2.2. Let G = (V, E) be an undirected graph and let I = (s;t1 , . . . ,tk ) be an instance of the
single source multicommodity flow problem such that for each i, s and ti are h-connected for a given
h ≥ 2. Then, for the duplex flows,
Fh,k (I) = F1 (I) ,
and moreover the equality can be achieved by a duplex flow with a total flow on each edge of at most
2 − 2/h.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 5
H. B RUHN , J. Č ERN Ý , A. H ALL , P. KOLMAN , AND J. S GALL
Note that Theorem 2.2 implies Theorem 2.1, with the exception of the half-integrality: we can use
the duplex flow scaled down so that we multiply a flow along each edge by a factor of 1/(2 − 2/h).
Nevertheless, we give also a direct proof of Theorem 2.1. One consequence of this proof is that in case
of h = 2, even the sharper bound can be achieved by a half-integral flow. Since for h = 2 the factor is
2 − 2/h = 1, and a trivial bound Fh (I) ≤ F1 (I) holds for every h, we have the following corollary which
shows that by imposing the requirement that the flow be a 2-route flow, we do not lose anything with
respect to the size of the flow.
Corollary 2.3. Let G = (V, E) be an undirected graph and let I = (s;t1 , . . . ,tk ) be an instance of the
single source multicommodity flow problem such that for each i, s and ti are 2-connected. Then
F1 (I) = F2 (I) .
In addition, the equality can be achieved by a half-integral 2-route flow.
Before proving the upper bounds, we first show, in Section 2.1, that for h-route flows with a single
source, the factor of 2 − 2/h is the best possible and also that the assumptions of single source and unit
capacity are essential. Then, in Section 2.2 we develop the common parts of the upper bound proofs and
finally in Sections 2.3 and 2.4 we show the upper bounds for non-duplex and duplex flows, respectively.
2.1 Lower bounds
Theorem 2.4. For every pair of integers h, k ≥ 2 there exist an undirected graph G and an instance
I = (s;t1 , . . . ,tk ) of the single source multicommodity flow problem such that for each i, s and ti are
h-edge-connected, and, at the same time,
2
F1 (I) ≥ 2 − · Fh (I) .
h
Proof. The set of vertices of the graph G consists of k + 2 distinct vertices s, v,t1 , . . . ,tk . The set of edges
contains h − 1 parallel edges between s and ti , and an edge between ti and v, for i = 1, . . . , k (Figure 1).
Consider the instance I = (s;t1 , . . . ,tk ). An elementary h-route flow between s and ti , for i = 1, . . . , k,
t1
t2
t3
s .. v
.
tk
Figure 1: The graph G for the lower bound
has to use two edges from the set F = {t j v} : j = 1, . . . k . Thus, the total h-route flow for the instance
I is upper bounded by h · |F|/2, that is, Fh (I) ≤ hk/2. On the other hand, F1 (I) = k(h − 1). This yields
the desired bound.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 6
S INGLE S OURCE M ULTIROUTE F LOWS AND C UTS
The situation is completely different for general multicommodity h-route flows. Even though the
maximum 2-route flow is as large as the maximum 1-route flow for single source multicommodity in-
stances, for general instances the ratio between the sizes of a maximum 1-route flow and a maximum
2-route flow is as large as k/2. On the other hand, a trivial upper bound on the ratio is F1 (I) ≤ kFh (I).
Theorem 2.5. For every pair of integers h, k ≥ 2 there exists a graph G = (V, E) and an instance I =
(s1 , . . . , sk ;t1 , . . . ,tk ) of the multicommodity flow problem such that for each i, the vertices si and ti are
h-connected, and, at the same time,
1
F (I) ≥ k 1 −
1
Fh (I) .
h
Proof. Let G be a graph on k + 1 distinct vertices v1 , . . . , vk+1 with vi connected by h − 1 parallel edges
with vi+1 , for i = 1, . . . , k, and vk+1 connected by an edge e with v1 (Figure 2). Consider an instance I
with si = vi and ti = vi+1 , for i = 1, . . . , k. Then, F1 (I) = k(h − 1). On the other hand, Fh (I) ≤ h, since
s1
e
tk s2 = t1
sk = t4 s3 = t2
s4 = t3
Figure 2: The graph G for h = 4 and k = 5
an elementary h-route flow between si and ti has to use the edge e = {vk+1 , v1 }, for every i = 1, . . . , k.
This yields the desired bound.
Theorem 2.1 relies on the assumption that the network has uniform edge capacities. The next theo-
rem shows that without this assumption, the result does not hold.
Theorem 2.6. For every C ≥ 1 and every integer h ≥ 1, there exists an undirected network G = (V, E)
with maximum edge capacity C and an instance I = (s;t1 , . . . ,tk ) of the single source multicommodity
flow problem such that for each i, F1 (s,ti ) = Fh (s,ti ), and, at the same time,
C−1
F (I) ≥
1
C− · Fh (I) .
h
Proof. Choose k = d(C(h−1)+1)/he and consider a network G with k +2 vertices V = {s, u,t1 ,t2 , . . .tk }
connected in the following way: s is connected with u by h edges, h − 1 of them with capacity C and
one with capacity 1, and for each i ∈ {1, . . . , k}, u and ti are connected by h edges, each of capacity 1
(Figure 3). Then, for an instance I = (s;t1 , . . . ,tk ) we have F1 (I) = C(h − 1) + 1 yet Fh (I) = h.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 7
H. B RUHN , J. Č ERN Ý , A. H ALL , P. KOLMAN , AND J. S GALL
t1
t2
s
u ..
.
tk
Figure 3: A bad network for nonuniform single source h-route flows (for h = 5).
2.2 Upper bounds: Preliminaries
In this section we cover three steps of the proof that are common for both non-duplex and duplex flows.
The first step is essentially an induction: We restrict ourselves to instances with several useful proper-
ties, using the fact that any potential minimal counterexample has these properties. Second, on these
instances, we choose some suitable maximal classical flow. Third, based on this flow, we define certain
auxiliary structures on the empty edges. In the last step of the proof, which is done in the next subsec-
tions separately for non-duplex and duplex flows, we use these empty edges to reroute some flow and
obtain an h-route flow of the appropriate size.
The following lemma shows that it is sufficient to prove Theorems 2.1 and 2.2 only for graphs
G = (V, E) and instances I = (s;t1 , . . . ,tk ) satisfying the following three properties:
A1 For each commodity i, the only minimum s − ti cut is the cut {ti } (we call it a trivial cut).
A2 In every integral maximum flow for the instance I, each empty edge is incident to at least one of
the sinks ti , and, moreover, if an empty edge is incident to exactly one sink, then the degree of the
sink is exactly h.
A3 Omitting any of the sinks from the instance I results in a decrease of the maximum flow (i. e., for
every i, if we denote by I−i the instance I without the sink ti , F1 (I−i ) < F1 (I)).
Lemma 2.7. Let G and I be a graph and an instance that represent a conterexample to Theorem 2.1
or Theorem 2.2 with minimal m + k (the number of edges plus the number of commodities). Then the
Properties A1-A3 hold.
Proof. Suppose we have a graph G and an instance I that do not satisfy the Properties A1-A3. We
construct a smaller graph G0 and an instance I0 such that the classical maximum flow is the same in both
cases and the maximal size of any type of h-route flow considered in the theorems can only decrease.
Thus if G and I violate any claim in the theorems, then also G0 and I0 violate it and the proof is completed.
A1. Assume that there exists a commodity i and a minimum cut C for the commodity that is not
trivial. Let δ j denote the connectivity of s and t j and let us denote by F an integral minimum cost
maximum flow for I. If the only commodity in the flow F that uses edges in the cut C is the commodity
i, we perform the following modification of G: the ti -side of G is merged into a single vertex t, that is,
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 8
S INGLE S OURCE M ULTIROUTE F LOWS AND C UTS
keep every edge on the s-side, remove every edge on the ti -side and for every edge {u, v} ∈ C with v
on the ti -side, replace {u, v} by a new edge {u,t}. We get a graph G0 that is smaller than G and for an
instance I0 = (s;t1 , . . .ti−1 ,t,ti+1 , . . . ,tk ) on G0 , the connectivity of s and t j is δ j for j ∈ {1, . . . , k}, j 6= i,
and the connectivity of s and t is δi , and the (classical) maximum flows for I in G and for I0 in G0 have
the same size. The graph G0 is smaller than G yet F1 (I) = F1 (I0 ) (note that multi-edges may occur).
Any h-balanced flow for I0 in G0 can be easily extended into an h-balanced flow of the same size for the
instance I in G.
If there are also some other commodities that use the cut C in the flow F, we redirect the part of
their flow going through C to ti . This is possible since the cut is minimal and there will be no other
commodities interfering. This way we maintain the same amount of the total flow and we argue as
before.
A2. From now on we assume that for every commodity, every minimum cut is the trivial one. We
denote by F an integral minimum cost maximum flow for I that does not satisfy the Property A2. Recall
that the cost is uniform, i. e., the cost of an integral flow is just the number of edges used.
Assume first that there exists an edge e that is empty in F and that is not incident to any of the sinks
ti . Since e is not incident to any terminal node and since for every i each minimum s − ti cut is the
trivial one, removing e from the graph G does not decrease the connectivity of any commodity and the
maximum flow for the instance I. As in the previous proof, an h-balanced flow for the smaller graph can
be interpreted as a solution for G.
Similarly, if there exists an edge e that is empty in F and that is incident to exactly one sink and the
degree of the sink is higher than h, deletion of e does not decrease the connectivity of any commodity
below h and it does not decrease the maximum flow for the instance I. Again, an h-balanced flow for
the smaller graph can be interpreted as a solution for G.
A3. Suppose that the graph G and the instance I do not satisfy the Property A3, that is, there exists a
commodity i such that F1 (I−i ) = F1 (I). We omit the commodity i to obtain the smaller instance I0 = I−i .
To finish the proof, note that all the reductions work also for half-integral and duplex h-route flows.
Let G and I be a graph and an instance satisfying the three properties A1-A3 and consider an arbitrary
integral minimum cost maximum flow for the instance I. By the characterization of h-route flows as h-
balanced flows (Theorem 1.1), the flow of every commodity with flow h or more is already an h-route
flow. Our aim is, for every commodity with flow less than h, to find new edge disjoint paths between the
source s and the relevant sink and to send some flow along each of them while not decreasing the flow
of other commodities much. For this process we start with a particular minimum cost maximum flow
that is described in Observation 2.8.
Given an integral flow for the instance I, we denote, for a non-terminal vertex v, the number of
empty edges incident to v by p(v), and we denote the number of empty edges connecting v and the sink
ti by mi (v). By the Property A2, we have ∑ki=1 mi (v) = p(v) for each non-terminal vertex v.
Observation 2.8. For the graph G and the instance I described above, there exists an integral minimum
cost maximum flow such that for every non-terminal vertex v and for every i:
• mi (v) ≤ dp(v)/2e.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 9
H. B RUHN , J. Č ERN Ý , A. H ALL , P. KOLMAN , AND J. S GALL
Moreover, in every integral minimum cost maximum flow, for every non-terminal vertex v and for every
i, the following holds:
• if mi (v) > p(v)/2 then there exists at least one flow path of a commodity other than i going
through v.
Proof. Consider an arbitrary integral minimum cost maximum flow and for a non-terminal vertex v
denote by r−i (v) the number of flow paths of commodities other than i passing through v. Note that all
empty edges incident to v are connected to a sink of degree exactly h (the Property A2). We are going
to observe that mi (v) < p(v)/2 + r−i (v), for every non-terminal vertex v and every commodity i.
Assume, for a contradiction, that mi (v) ≥ p(v) − mi (v) + 2r−i (v) for some v and i, and consider the
s − ti cut {v,ti }. Due to our assumption, the size of this cut is smaller than or equal to the size of the
trivial s − ti cut {ti } which is a contradiction with the Property A1. This completes the proof of the
second part of Observation 2.8.
t2
t1
v
p3 p4
p2
p1
s
Figure 4: An example of a non-terminal vertex v satisfying the first property of Observation 2.8. Dashed
lines represent empty edges and solid lines represent flow paths. We have p(v) = 6, m1 (v) = 3, m2 (v) = 3
and r−1 (v) = 3.
Now, if there is a non-terminal vertex v and a commodity i with mi (v) > dp(v)/2e, then there are
r−i (v) > mi (v) − p(v)/2 flow paths of other commodities passing through v. Choose one of them, say a
path p of a commodity j, and reroute it to ti . To be more precise, the new path goes from the source s to
the vertex v along the original path p, and then it continues to ti along one of the empty edges connecting
v and ti . After the modification, mi (v) decreases by one and m j (v) increases by one; the cost and the size
of the total flow are not affected. This way we continue until mi (v) ≤ dp(v)/2e for every i. Notice that
the changes done in the flow around v will not destroy the desired property for any other vertex.
We apply the same rerouting procedure for every other non-terminal vertex v0 for which there exists
a commodity i0 such that mi0 (v0 ) > dp(v0 )/2e.
From now on we fix some minimum cost maximum flow satisfying Observation 2.8 and denote it F.
By the choice of F and by the Property A2, each empty edge is incident either to two different sinks or
to a sink and to a vertex adjacent to another sink; the last assertion holds since otherwise there exists a
smaller cost flow of the same size. The idea of the proof is to exploit these empty edges to reroute some
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 10
S INGLE S OURCE M ULTIROUTE F LOWS AND C UTS
flow from other commodities to each sink with flow less than h. If we succeed to provide a non-zero
flow along at least h edges to each sink, we get a non-zero h-balanced flow for each commodity.
We define an auxiliary structure, called octopus, which will help us to organize the rerouting. For-
mally, an octopus is a (multi)graph that is a union of edge disjoint paths of length one and two that start
in the same vertex; the paths are called tentacles. If an octopus O is a subgraph of the graph G and the
initial vertex of the paths (i. e., of the tentacles) is a vertex v, we say that the octopus is sitting in v.
Figure 5: An octopus
For every commodity i with flow smaller than h, we define an octopus Oi . The octopus Oi is sitting
in the terminal ti and has h − fi tentacles, where fi denotes the amount of flow of a commodity i in F, and
the tentacles reach through different empty edges to neighboring vertices (if there are more than h − fi
empty edges incident to ti , we choose any h − fi of them). Later we will amend the octopuses, namely
we will lengthen some of the tentacles.
Consider a non-terminal vertex v. The Property A2 implies that the number of tentacles reaching
v is p(v) and we denote them by τ1 , . . . , τ p(v) . If none of the octopuses reaches v by more than p(v)/2
tentacles, there exists a permutation π of the tentacles τ1 , . . . , τ p(v) which consists only of 2-cycles and
possibly one 3-cycle such that tentacles τl and π(τl ) belong to different octopuses. For example, always
greedily form a 2-cycle between tentacles of two distinct octopuses with the maximal number of remain-
ing tentacles ending in v. Do this until 2 or 3 tentacles remain (depending on the parity of p(v)), and
then form the last cycle (only this last cycle can be a 3-cycle). We lengthen the tentacle τl through the
edge used by the tentacle π(τl ) so that τl now terminates in the sink in which the octopus with tentacle
π(τl ) is sitting.
If there exists an octopus Oi that reaches the non-terminal vertex v by more than p(v)/2 tentacles,
then such an octopus is exactly one. For such an octopus, by Observation 2.8, the number of its tentacles
reaching v is exactly dp(v)/2e. There exists a permutation π of p(v) − 1 tentacles reaching v such that
it consists of 2-cycles of tentacles belonging to different octopuses, namely a matching of all but one
tentacles of Oi to all the others. In a similar way as before, each tentacle τ involved in the permutation
is lengthened to the sink in which the octopus with the tentacle π(τ) is sitting. Recall that by Observa-
tion 2.8 there exists a flow path passing through v that does not belong to the commodity i, and by the
minimality of the cost of the flow F, the terminal vertex of the path is adjacent to v.
At this point, each tentacle of an octopus reaches either another terminal vertex (we say that the
tentacle touches the corresponding commodity), or a flow path of another commodity that no other
tentacle reaches (again we say that the tentacle touches the corresponding commodity). Moreover, each
tentacle τ is stretched only through empty edges and at most one tentacle is stretched through each
empty edge in each direction; if there are two tentacles stretched through the same edge (in opposite
direction) they belong to different octopuses.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 11
H. B RUHN , J. Č ERN Ý , A. H ALL , P. KOLMAN , AND J. S GALL
Observation 2.9. For each i, the number of tentacles that touch the commodity i is strictly less than fi .
Proof. Were it not the case, it would be possible to redirect the complete flow of the commodity i,
through the tentacles touching it, to other terminals without decreasing the total flow, contradicting the
Property A3.
2.3 Upper bounds: Non-duplex flows
Proof of Theorem 2.1. We start by constructing the half-integral h-route flow of size (at least) F1 (I)/2.
Then we explain how to increase the size of the flow to (at least) F1 (I)/(2 − 2/h).
For each tentacle of the octopus Oi touching the commodity j 6= i, we reroute a half unit of the flow of
a commodity j to ti along the edges that the corresponding tentacle is stretched through. Observation 2.9
guarantees that every commodity j has enough flow to provide a half unit for each tentacle touching it
and yet to keep more than f j /2 units for itself. We decrease the flow of every unaffected path to one
half.
At this point, the amount of flow of a commodity i with fi < h is h/2 and the amount of flow of a
commodity i with fi ≥ h is fi /2. Moreover, since the initial flow was integral (flow paths from source to
terminals were disjoint), the new flow paths of each individual commodity will be edge disjoint. Thus,
we have an h-balanced flow of size at least F(I)/2, for the instance I, and by construction, the flow is
half integral.
To prove the sharper bound (not necessarily with half-integral flows) we observe that for every
commodity with flow at most h − 1 in the initial flow, its h-balanced flow at the end is at least h/2 which
corresponds to the ratio 2 − 2/h. The only problem is with commodities with original flow h or more.
Thus, if we manage to slightly increase the final flow of these commodities, the proof is completed.
Recall that no octopus is sitting in a terminal vertex of a commodity with flow h or more.
We proceed as follows: every commodity t j with initial flow h or more will demand a tax of 1/(2h −
2) units of flow for each path that it provided to another commodity. Commodities are able to pay these
taxes since every commodity had initial flow that was at least one greater than the number of tentacles
touching it (Observation 2.9) and every commodity requires help from at most h − 1 other commodities
(more precisely, needs at most h − 1 new edge disjoint paths). In the worst case, it keeps (only) a half
unit of flow for itself and spends the other half on taxes for the h − 1 helpers.
tax tj
ti tax tj
ti
v
0.5 0.5
0.5 0.5
s s
Figure 6: Taxation: on the left side is depicted the case when a tentacle touches a terminal vertex, and
on the right side is depicted the case when a tentacle touches a path of other commodity.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 12
S INGLE S OURCE M ULTIROUTE F LOWS AND C UTS
The flow corresponding to a tax of a commodity ti paid to a commodity t j flows from s to ti along an
original path of a commodity i and then from ti to t j along the tentacle of the octopus sitting in ti ; in the
case of an octopus Oi touching a path of the commodity j (and not directly touching the sink t j ) the flow
flows from s to ti along an original path of the commodity i, then along the tentacle of the octopus Oi
and finally along an edge of the flow path of the commodity j that the tentacle of Oi touches. In addition
to this, we set the flow along each path that was unaffected by the rerouting process to 1/(2 − 2/h) (and
not to 1/2 as we did for the half-integral flow). In this way, a commodity with an initial flow fi ≥ h will
have a final h-balanced flow at least fi (h/(2h − 2)), which corresponds to an h-route flow of the same
size.
Concerning the proof of Theorem 2.3, namely the half-integrality, notice that for h = 2 the taxes in
the previous proof are equal to 1/2. Thus the resulting flow is half-integral.
2.4 Upper bound: Duplex flows
Proof of Theorem 2.2. We now construct an h-balanced duplex flow of the same size as the original flow
F1 (I). To do this, for each octopus Oi we reroute some flow from other sinks to the sink ti . More exactly,
for a certain amount zi ∈ [0, 1], we reroute zi units of the flow along each of the tentacles of Oi to ti . At
the same time, we guarantee that from the original flow fi to ti , exactly fi (1 − zi ) units are rerouted to
other sinks using their octopuses. If this rerouted flow is taken evenly from all fi incoming paths, then
the resulting flow of the commodity i has size at least hzi and thus it is an h-route flow. If a tentacle of
Oi touches a flow path of a commodity j at v which is not the sink t j , then we take zi / f j units of the
rerouted flow from this flow path and the remaining flow is routed from t j back one edge along to v. (Cf.
the last paragraph of the proof.)
The choice of zi guarantees that the commodities with original flow less than h can be rerouted.
On the other hand, each commodity with flow h or more is touched by less then h tentacles due to
Observation 2.9. Consequently there is enough original flow for the rerouting and if taken evenly from
all paths, the flow of this commodity is also an h-route flow afterwards. After the rerouting, each edge
has in each direction a flow of at most 1, either at most 1 from the original flow or at most zi ≤ 1 from
the rerouting along one tentacle.
It remains to guarantee the existence of numbers zi described above. For simplicity, renumber the
commodities so that the first k0 sinks ti are exactly those with the initial flow fi < h, that is, exactly those
with an octopus. Let ai j be the number of tentacles of O j touching the commodity i. We need the values
zi to satisfy, for each i ≤ k0 ,
k0
∑ ai j z j = fi (1 − zi ) . (2.2)
j=1
0 0
Define a function F : Rk → Rk so that its ith coordinate is
0
1 k
(F(~z))i = 1 − ∑ ai j z j .
fi j=1
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 13
H. B RUHN , J. Č ERN Ý , A. H ALL , P. KOLMAN , AND J. S GALL
Then the system of equations (2.2) is equivalent to the equation ~z = F(~z). Due to Observation 2.9 we
know that for each i ≤ k0
k0
∑ ai j < fi . (2.3)
j=1
0
This implies that F maps the unit cube [0, 1]k to itself. Obviously, F is continuous as it is a linear
function. Using Brouwer’s fixed-point theorem (which asserts that any continuous mapping from a ball
to itself has a fixed point) and the fact that a ball and a cube are homeomorphic, we conclude that F has
a fixed point, that is, the equation~z = F(~z) has a solution. This solution also satisfies the system (2.2),
which concludes the proof. Note that the proof is still constructive, since F is linear and we can find the
solution efficiently.
In fact, inequalities (2.3) imply that F is a strong contraction under the l∞ norm, which means that
0
there exists a constant α < 1 such that for any ~y,~z ∈ [0, 1]k , it holds that
kF(~z) − F(~y)k∞ ≤ α · k~z −~yk∞ ,
0
where k~zk∞ = maxi=1,...,k0 |zi |. For the constant α = maxi=1,...,k0 (∑kj=1 ai j / fi ) the strong contraction prop-
erty follows easily for each coordinate of F(~z) − F(~y) by subtracting the defining equations for (F(~z))i
and (F(~y))i . The strong contraction property implies that in the unit cube, there exists a (unique) solu-
tion of the equation ~z = F(~z), namely a limit of points obtained by repeated applications of F, starting
at any point x the unit cube. (Note that the distances between subsequent points in the sequence x,
F(x), F(F(x)), etc., decrease in a geometric sequence due to the contraction property.) This gives an
alternative elementary proof without use of Brouwer’s theorem.
To prove the second part of Theorem 2.2, we slightly modify the octopuses. In the case of a non-
terminal vertex v and a 3-cycle (i jl) in the permutation π used for extending the tentacles, we do not
extend the tentacles along the cycle but instead we split each tentacle into two halves and extend them to
the remaining two vertices. Thus this 3-cycle will contribute 1/2 to each ai j , a jl , ali , a ji , al j , ail . Then,
for example, the edge vti will have flow zi to ti and (z j + zl )/2 from ti .
The same argument as above guarantees that the system of equations (2.2) has again a solution in
the unit cube, with flow at most 1 in each direction along any edge. It remains to verify that on any edge,
the sum of flows in both directions is at most 2 − 2/h. There are three types of such edges.
1. An edge used by two tentacles, one tentacle of Oi touching the commodity j and one tentacle
of O j touching the commodity i. This may be an edge tit j , or an edge incident to a non-terminal v and
involved in a 2-cycle (i j) of the permutation π. The total flow is zi + z j . We have fi , f j ≤ h − 1 as there
are octopuses at ti and t j , and the corresponding equations in (2.2) imply (after removing the left-hand
side terms for other tentacles) that z j ≤ (h − 1)(1 − zi ) and zi ≤ (h − 1)(1 − z j ). Adding these inequalities
and dividing by h we obtain the desired bound zi + z j ≤ 2 − 2/h.
2. An edge vti with a non-terminal vertex v and involved in a 3-cycle (i jl) of π. This edge has total
flow zi + (z j + zl )/2. Again fi , f j , fl ≤ h − 1 and the corresponding equations in (2.2) imply
2(h − 1)zi + z j + zl ≤ 2(h − 1) ,
zi + 2(h − 1)z j + zl ≤ 2(h − 1) ,
zi + z j + 2(h − 1)zl ≤ 2(h − 1) .
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 14
S INGLE S OURCE M ULTIROUTE F LOWS AND C UTS
Adding the first inequality multiplied by 2(h − 1) and the remaining two inequalities multiplied by h − 2
yields the desired bound.
3. An edge vt j for a tentacle of Oi touching the commodity j at a non-terminal vertex v. The
flow is at most 1 − zi / f j of the original flow to t j , and zi − zi / f j of the flow that is rerouted from t j .
Since zi ≤ 1, it suffies to show that f j ≤ h to conclude that the total flow on the edge vt j is at most
1 + zi (1 − 2/ f j ) ≤ 2 − 2/h. We argue as follows. If we redirect the unit of the original flow going
through the edge vt j to the sink vi , we get another maximal flow with an empty edge adjacent to t j . By
the Property A2 the degree of t j is at most h which in turn implies that f j ≤ h.
3 Disconnecting cuts
We will denote the size of a minimum h-disconnecting cut for an instance I by Ch (I).
Theorem 3.1. For every h ≥ 2 and every instance I of the single source flow problem,
Fh (I)
2
≤ C (I) ≤ 2 −
h · Fh (I) . (3.1)
h h
Moreover, for every h ≥ 2 and every ε > 0 there exists an instance I = {s;t} of the problem such that
(1 − ε) · Fh (I) ≤ Ch (I) , (3.2)
and for every k ≥ 1 and every h ≥ 2 there exists an instance I such that
Fh (I)
= Ch (I) . (3.3)
h
Proof. Given a decomposition of an h-route flow into a linear combination of elementary h-route flows,
we have to cut at least one of the h paths of every h-system in the decomposition. Altogether we have to
cut edges of total capacity at least Fh (I)/h which proves the first inequality.
To prove the inequality Ch (I) ≤ (2 − 2/h) · Fh (I) we observe that a minimum classical cut is also
an h-cut, and from the duality of flows and cuts we know that the size of this cut is equal to F1 (I). We
apply the bound F1 (I) ≤ (2 − 2/h) · Fh (I) of Theorem 2.1 (without loss of generality we assume that all
sinks in the instance I are h-connected with the source) and the proof is completed.
Concerning the second part of the theorem, consider a graph consisting of two vertices s and t
connected by m parallel edges, with m ≥ h. The maximum h-route flow has size m and the minimum
h-disconnecting cut has size m − (h − 1). We conclude that for every ε > 0 there exists an integer m
such that (m − h + 1)/m ≥ 1 − ε and, thus, there exists an instance I = {s;t} satisfying the inequality
(3.2). Note that a fractional disconnecting cut is in this case (almost) h-times better: take a fraction 1/h
of each edge in the cut.
For the last part of the theorem, consider the instance and the network in Figure 3 with every edge
capacity set to one. Then, Fh (I) = hk and Ch (I) = k.
The proof above implies that the minimal classical cut is a good approximation for the h-
disconnecting problem. It can be found efficiently, and thus we have:
Corollary 3.2. For every h ≥ 2, there exists a polynomial time (2h − 2)-approximation algorithm for
the h-disconnecting problem with a single source.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 15
H. B RUHN , J. Č ERN Ý , A. H ALL , P. KOLMAN , AND J. S GALL
Remark. The bound on the performance of the algorithm is not far from what happens for “bad”
instances. Think about a simple graph consisting of two vertices u, v connected by h parallel edges and
an instance with one commodity with source in u and sink in v: the minimum disconnecting cut has size
1 while the disconnecting cut obtained by the algorithm has size h.
We also note that the bound (3.1) can be slightly improved to
Fh (I)
2
≤ Ch (I) ≤ 2− · Fh (I) − (h − 1)
h h
by deleting all but h − 1 edges from the minimum classical cut (instead of deleting all the edges). If
there is only one commodity, this slightly modified procedure computes an optimal h-disconnecting cut.
4 Open problems
We conclude with two open problems about disconnecting cuts for multiroute flows. The approximation
ratio of the algorithm for disconnecting cuts for single source flow problems described in the last section
is 2h − 2; design a better algorithm. Similarly, design an approximation algorithm for the disconnecting
cut problem for the more general multiroute multicommodity flow problems (e. g., single source and
non-uniform capacities, multiple sources and uniform capacities). As the close relation between classical
flows and multiroute flows is lost in these cases, a novel approach will be needed.
Acknowledgment The authors thank Neal Young and Yefim Dinitz for stimulating discussions.
References
[1] * C HARU C. AGGARWAL AND JAMES B. O RLIN: On multiroute maximum flows in networks.
Networks, 39:43–52, 2002. [Wiley:10.1002/net.10008]. 1, 1.1, 1.1
[2] * R. K. A HUJA , T. L. M AGNANTI , AND J. B. O RLIN: Network Flows: Theory, Algorithms and
Applications. Prentice-Hall, 1993. 1
[3] * YONATAN AUMANN AND Y UVAL R ABANI: An O(log k) approximate min-cut max-flow
theorem and approximation algorithm. SIAM Journal on Computing, 27(1):291–301, 1998.
[SICOMP:10.1137/S0097539794285983]. 1.1
[4] * A MITABHA BAGCHI , A MITABH C HAUDHARY, AND P ETR KOLMAN: Short length Menger’s
theorem and reliable optical routing. Theoretical Computer Science, 339:315–332, 2005.
[TCS:10.1016/j.tcs.2005.03.009]. 1.1
[5] * A MITABHA BAGCHI , A MITABH C HAUDHARY, P ETR KOLMAN , AND C HRISTIAN S CHEI -
DELER : Algorithms for fault-tolerant routing in circuit switched networks. SIAM Journal on
Discrete Mathematics, 21:141–157, 2007. [SIDMA:10.1137/S0895480102419743]. 1.1
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 16
S INGLE S OURCE M ULTIROUTE F LOWS AND C UTS
[6] * A MITABHA BAGCHI , A MITABH C HAUDHARY, P ETR KOLMAN , AND J I Ř Í S GALL: A simple
combinatorial proof for the duality of multiroute flows and cuts. Technical Report 2004-662,
Charles University, Prague, 2004. 1, 1.1, 1.1
[7] * G EORG BAIER , E KKEHARD KOEHLER , AND M ARTIN S KUTELLA: The k-splittable flow prob-
lem. Algorithmica, 42(3–4):231–248, 2005. [Algorithmica:jtl3r3k633523486]. 1.1
[8] * A LOK BAVEJA AND A RAVIND S RINIVASAN: Approximation algorithms for disjoint paths and
related routing and packing problems. Mathematics of Operations Research, 25(2):255–280, 2000.
1.1
[9] * H ENNING B RUHN , JAKUB Č ERN Ý , A LEXANDER H ALL , AND P ETR KOLMAN: Single source
multiroute flows and cuts on uniform capacity networks. In Proc. 18th Ann. ACM-SIAM Symposium
on Discrete Algorithms (SODA’07), pp. 855–863. SIAM, 2007. [SODA:1283383.1283475]. ∗
[10] * A MIT C HAKRABARTI , C HANDRA C HEKURI , A NUPAM G UPTA , AND A MIT K UMAR: Approx-
imation algorithms for the unsplittable flow problem. Algorithmica, 47(1):53–78, 2007. [Algorith-
mica:m5710531h2514815]. 1.1
[11] * C HANDRA C HEKURI AND S ANJEEV K HANNA: Edge-disjoint paths revisited. ACM Transac-
tions on Algorithms, 3, 2007. [ACM:1290672.1290683]. 1.1
[12] * I SRAEL C IDON , R APHAEL ROM , AND Y UVAL S HAVITT: Analysis of multi-path routing. IEEE/
ACM Transactions on Networking, 7(6):885–896, 1999. [ACM:323983.323992]. 1.1
[13] * Y. D INITZ , N. G ARG , AND M. G OEMANS: On the single source unsplittable flow problem.
Combinatorica, 19(1):17–41, 1999. [Springer:pg0crc9nqlfdmajj]. 1.1
[14] * D. D U AND R. C HANDRASEKARAN: The multiroute maximum flow problem revisited. Net-
works, 47(2):81–92, 2006. [Wiley:10.1002/net.20099]. 1.1
[15] * D ONGLEI D U: Multiroute Flow Problem. Ph.D. thesis, The University of Texas at Dallas, 2003.
1.1
[16] * T HOMAS E RLEBACH AND A LEXANDER H ALL: NP-hardness of broadcast scheduling and in-
approximability of single-source unsplittable min-cost flow. Journal of Scheduling, 7(3):223–241,
2004. [Springer:h57n764rq0124578]. 1.1
[17] * L. R. F ORD AND D. R. F ULKERSON: Maximum flow through a network. Canad. J. Math.,
8:399–404, 1956. 1.1
[18] * NAVEEN G ARG , V IJAY V. VAZIRANI , AND M IHALIS YANNAKAKIS: Approximate max-flow
min-cut theorems and their applications. SIAM Journal on Computing, 25(2):235–251, 1996.
[SICOMP:10.1137/S0097539793243016]. 1.1
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 17
H. B RUHN , J. Č ERN Ý , A. H ALL , P. KOLMAN , AND J. S GALL
[19] * V. G URUSWAMI , S. K HANNA , R. R AJARAMAN , B. S HEPHERD , AND M. YANNAKAKIS: Near-
optimal hardness results and approximation algorithms for edge-disjoint paths and related prob-
lems. Journal of Computer and System Sciences, 67(3):473–496, 2003. [JCSS:10.1016/S0022-
0000(03)00066-7]. 1.1
[20] * KOUSHIK K AR , M URALI KODIALAM , AND T. V. L AKSHMAN: Routing restorable bandwidth
guaranteed connections using maximum 2-route flows. IEEE/ACM Transactions on Networking,
11:772–781, 2003. [ACM:948928.948935]. 1.1
[21] * WATARU K ISHIMOTO: A method for obtaining the maximum multiroute flows in a network.
Networks, 27(4):279–291, 1996. 1, 1.1
[22] * WATARU K ISHIMOTO AND M. TAKEUCHI: On m-route flows in a network. IEICE Transactions,
J-76-A(8):1185–1200, 1993. (in Japanese). 1.1
[23] * J. M. K LEINBERG: Single-source unsplittable flow. In Proc. 37th FOCS, pp. 68–77. IEEE
Computer Society Press, 1996. [FOCS:10.1109/SFCS.1996.548465]. 1.1
[24] * RONALD KOCH , M ARTIN S KUTELLA , AND I NES S PENKE: Approximation and complexity
of k-splittable flows. In Proceedings of the Third Workshop on Approximation and Online Al-
gorithms, volume 3879 of Lecture Notes in Computer Science, pp. 244–257. Springer, 2005.
[WADS:l871111265475j11]. 1.1
[25] * S TAVROS G. KOLLIOPOULOS AND C LIFFORD S TEIN: Approximation algorithms for
single-source unsplittable flow. SIAM Journal on Computing, 31(3):919–946, 2002.
[SICOMP:10.1137/S0097539799355314]. 1.1
[26] * P ETR KOLMAN AND C HRISTIAN S CHEIDELER: Simple on-line algorithms for the maximum
disjoint paths problem. Algorithmica, 39(3):209–233, 2004. [Algorithmica:ppc4pcxagm69d4jv].
1.1
[27] * P ETR KOLMAN AND C HRISTIAN S CHEIDELER: Improved bounds for the unsplittable flow
problem. Journal of Algorithms, 61(1):20–44, 2006. [Elsevier:10.1016/j.jalgor.2004.07.006]. 1.1
[28] * T OM L EIGHTON AND S ATISH R AO: Multicommodity max-flow min-cut theorems and their use
in designing approximation algorithms. Journal of the ACM, 46(6):787–832, November 1999.
[JACM:331524.331526]. 1.1
[29] * N. L INIAL , E. L ONDON , AND Y U . R ABINOVICH: The geometry of graphs and some of its
algorithmic applications. Combinatorica, 15(2):215–245, 1995. 1.1
[30] * M AREN M ARTENS AND M ARTIN S KUTELLA: Flows on few paths: Algorithms and lower
bounds. Networks, 48(2):68–76, 2006. [Wiley:10.1002/net.20121]. 1.1
[31] * M AREN M ARTENS AND M ARTIN S KUTELLA: Length-bounded and dynamic k-splittable flows.
In Operations Research Proceedings 2005, pp. 297–302, 2006. [Springer:w2u3032j1804481t].
1.1
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 18
S INGLE S OURCE M ULTIROUTE F LOWS AND C UTS
[32] * K. M ENGER: Zur allgemeinen Kurventheorie. Fundam. Math., 10:96–115, 1927. 1.1
[33] * M. S KUTELLA: Approximating the single source unsplittable min-cost flow problem. Mathe-
matical Programming, Ser. B, 91(3):493–514, 2002. [Springer:txfq9gvdtw0cac0g]. 1.1
[34] * A RAVIND S RINIVASAN: Improved approximations for edge-disjoint paths, unsplittable flow, and
related routing problems. In Proc. 38th FOCS, pp. 416–425. IEEE Computer Society Press, 20–22
1997. [FOCS:10.1109/SFCS.1997.646130]. 1.1
AUTHORS
Henning Bruhn [About the author]
Mathematisches Seminar, Universität Hamburg, Germany
bruhns math uni-hamburg de
http://www.math.uni-hamburg.de/home/bruhn/
Jakub Černý [About the author]
Department of Applied Mathematics, Faculty of Mathematics and Physics
Charles University, Czech Republic
kuba kam mff cuni cz
http://kam.mff.cuni.cz/~kuba/
Alexander Hall [About the author]
Google Switzerland GmbH, Zurich, Switzerland
alex hall gmail com
Petr Kolman [About the author]
Department of Applied Mathematics, Faculty of Mathematics and Physics
Charles University, Czech Republic
kolman kam mff cuni cz
http://kam.mff.cuni.cz/~kolman/
Jiřı́ Sgall [About the author]
Institute of Mathematics, AS ČR, Czech Republic
sgall math cas cz
http://www.math.cas.cz/~sgall/
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 19
H. B RUHN , J. Č ERN Ý , A. H ALL , P. KOLMAN , AND J. S GALL
ABOUT THE AUTHORS
H ENNING B RUHN has been a postdoc at Universität Hamburg. since summer 2006. In
2005 he obtained his Ph. D. under the supervision of Reinhard Diestel. He spent the
following year in Grenoble learning combinatorial optimisation and French. He likes
rock climbing and tries to learn Japanese.
A LEXANDER H ALL received a Master’s degree (“Diplom”) in Computer Science at the
Technische Universität München in 1998. In December 2003 he completed his doctoral
studies in the group of Thomas Erlebach at the ETH Zürich and received a Ph. D. for his
thesis “Scheduling and Flow-Related Problems in Networks.” After being a post-doc at
ETH Zürich and UC Berkeley, he is now with Google in Zurich.
JAKUB Č ERN Ý is finishing his Ph. D. at the Department of Applied Mathematics of Charles
University in Prague. His advisor is Pavel Valtr. He is interested in computational and
discrete geometry and efficient algorithms in general. His hobbies are Aikido, improvi-
sational comedy theatre, outdoor activities.
P ETR KOLMAN is an Assistant Professor at Charles University in Prague, Czech Republic.
After obtaining his Ph. D., he spent a year at the Heinz Nixdorf Institut at the University
of Paderborn, Germany and a year at the University of California, Riverside.
J I Ř Í S GALL grew up in Prague, Czechoslovakia, where he received his RNDr. degree
(equivalent of Master’s) at Charles University under supervision of Antonı́n Sochor.
Then he went to Carnegie Mellon University and received his Ph. D. under the super-
vision of Steven Rudich. After that he went back to Prague, Czech Republic, where
he is now a senior researcher at the Institute of Mathematics of the Academy of Sci-
ences of the Czech Republic. His main research interests are online and approximation
algorithms for scheduling and other combinatorial problems. He also worked in com-
munication complexity and proof complexity.
T HEORY OF C OMPUTING, Volume 4 (2008), pp. 1–20 20