Routing with Congestion in Acyclic Digraphs
Saeed Akhoondian Amiri1 , Stephan Kreutzer∗1 , Dániel Marx2 , and
Roman Rabinovich1
1

Technical University Berlin, Sekr TEL 7-3, Ernst-Reuter-Platz 7, 10587 Berlin,
Germany,
{saeed.amiri,stephan.kreutzer,roman.rabinovich}@tu-berlin.de
Institute for Computer Science and Control, Hungarian Academy of Sciences
(MTA SZTAKI) dmarx@cs.bme.hu.

2

arXiv:1605.01866v1 [] 6 May 2016

Abstract
We study the version of the k-disjoint paths problem where k demand pairs (s1 , t1 ), . . . , (sk , tk )
are specified in the input and the paths in the solution are allowed to intersect, but such that no
vertex is on more than c paths. We show that on directed acyclic graphs the problem is solvable
in time nO(d) if we allow congestion k − d for k paths. Furthermore, we show that, under a
suitable complexity theoretic assumption, the problem cannot be solved in time f (k)no(d/ log d)
for any computable function f .
Digital Object Identifier 10.4230/LIPIcs...

1

Introduction

The k-disjoint paths problem and related routing problems are among the central problems
in combinatorial optimisation. In the most basic variant of the k-disjoint paths problem,
a graph G is given with k pairs (s1 , t1 ), . . . , (sk , tk ) of vertices and the task is to find k
pairwise vertex-disjoint paths linking each si to its corresponding target ti .
The problem is well known to be NP-complete [14]. On undirected graphs with a fixed
number k of source/terminal pairs, Robertson and Seymour proved in their monumental
graph minor series [21] that the problem is polynomial-time solvable. In fact, they showed
that it is fixed-parameter tractable with parameter k: it can be solved in cubic time for every
fixed value of k.
For directed graphs, the problem is computationally much harder. Fortune et al. [15]
proved that it is already NP-complete for only k = 2 source/terminal pairs. In particular,
this also implies that it is not fixed-parameter tractable on directed graphs. Following this
result a lot of work has gone into establishing more efficient algorithms on restricted classes
of digraphs.
Fortune et al. [15] showed that the problem can be solved in time nO(k) on acyclic
digraphs, that is, it is polynomial-time for every fixed k. However, as proved by Slivkins [22],
the problem is W [1]-hard on acyclic digraphs, and therefore unlikely to be fixed-parameter
tractable. On the other hand, Cygan et al. [11] proved that the problem is fixed-parameter
tractable with parmeter k when restricted to planar digraphs. Related to this, Amiri et
al. [1] proved that the problem remains NP-complete even in upward planar graphs, but
admits a single exponential fixed-parameter algorithm.

∗

The research of Saeed Amiri, Stephan Kreutzer and Roman Rabinovich has been supported by the
European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation
programme (ERC consolidator grant DISTRUCT, agreement No 648527). The research of Dániel Marx
was supported by ERC Starting Grant PARAMTIGHT (No. 280152) and OTKA grant NK105645.
licensed under Creative Commons License CC-BY
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

XX:2

Routing with Congestion in Acyclic Digraphs

Disjoint paths problems have also been studied intensively in the area of approximation
algorithms, both on directed and undirected graphs (see, e.g., [2, 4–10, 18]). The goal is,
given an input graph G and demands (s1 , t1 ), . . . , (sk , tk ) to route as many pairs as possible
in polynomial time. There are many variations what it means for a pair to be routable. In
particular, a problem studied intensively in the approximation literature is a relaxed version
of disjoint paths where the paths are no longer required to be fully disjoint. Instead, they
may intersect but every vertex of the graph is allowed to be contained in at most c paths,
for some fixed constant c. This is called congestion c routing. In particular, the well-linked
decomposition framework developed in [10] for undirected graphs and later generalised to
digraphs in [7] has proved to be very valuable for obtaining good approximation algorithms
for disjoint paths problems on planar graphs and digraphs.
In this paper, we are interested in exact solutions for high congestion routing on acyclic
digraphs. More precisely, we study the following problem.
I Definition 1. 1. Let G be a digraph and let I := {(s1 , t1 ), . . . , (sk , tk )} be a set of pairs
of vertices. Let c ≥ 1. A c-routing of I is a set {P1 , . . . , Pk } of paths such that, for all
1 ≤ i ≤ k, path Pi links si to ti and no vertex v ∈ V (G) appears in more than c paths
from {P1 , . . . , Pk }.
2. Let k, c ≥ 1. In the (k, c)-Congestion Routing problem, a digraph G is given in the
input together with a set I := {(s1 , t1 ), . . . , (sk , tk )} of k pairs of vertices (the demands);
the task is to decide whether there is a c-routing of I in G.
We consider (k, c)-Congestion Routing on acyclic digraphs. First, it is not very
difficult to show that, for every fixed c ≥ 1, we can generalize the nO(1) time algorithm of
Fortune et al. [15] to (k, c)-Congestion Routing. By revisiting the W[1]-hardness proof
of Slivkins [22] and making appropriate modifications, we can establish that the problem
remains W[1]-hard for every fixed congestion c ≥ 1. Moreover, by doing the proof in a
more modern way (reducing from general subgraph isomorphism instead of maximum clique
and invoking a lower bound of Marx [20]), we can show that the nO(k) time algorithm is
essentially best possible with respect to the exponent of n. This lower bound is under the
Exponential-Time Hypothesis (ETH), which can be informally stated as n-variable 3Sat
cannot be solved in time 2o(n) (see [12, 16, 19] for more background).
I Theorem 2. For any fixed integer c ≥ 1, (k, c)-Congestion Routing is W[1]-hard
parameterized by k and, assuming ETH, cannot be solved in time f (k)no(k/ log k) for any
computable function f .
While Theorem 2 shows that the problem does get easier for any larger fixed congestion
c ≥ 1, intuitively one expects the problem to get simpler at some point: after all, the problem
is trivial if c ≥ k. Therefore, we study the complexity of the problem in settings close to this
extreme case. The main algorithmic result of this paper is to show that for any fixed value
of d ≥ 1, the (k, k − d)-Congestion Routing problem can be solved in time nO(d) . That
is, the exponent of the polynomial bounding the running time of the algorithm only depends
on d but not on the number k.
I Theorem 3. For every fixed d ≥ 1, the (k, k − d)-Congestion Routing problem on
acyclic digraphs can be solved in time nO(d) .
A simple corollary of Theorem 2 shows that (k, k − d)-Congestion Routing is unlikely
to be fixed-parameter tractable and the running time of Theorem 3 essentially cannot be
improved (assuming ETH). Observe that if we set d := k − 1, then (k, k − d)-Congestion

Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, Roman Rabinovich

Routing is simply the standard k-disjoint path problem, thus any algorithmic result for
(k, k − d)-Congestion Routing parameterized by d would imply the essentially same
algorithmic result for the fully disjoint version parameterized by k.
I Corollary 4. (k, k − d)-Congestion Routing is W[1]-hard parameterized by d (if k
is part of the input) and, assuming ETH, cannot be solved in time f (k)no(d/ log d) for any
computable function f .
Organisation.
The paper is organised as follows. In Section 3 we fix some notation
and prove our main algorithmic result. The corresponding lower bound in then proved in
Section 4.

2

Preliminaries

We review basic notation and concepts of graph theory needed in the paper. We refer to
[3, 13] for background.
Let G be a digraph. We write V (G) and E(G) for its set of vertices and edges, respectively.
We assume that there is no edge with the same head and tail, i.e. there are no loops in the
digraphs we consider in this paper. If (u, v) ∈ E(G) is an edge, then u is its tail and v is its
head. G is simple if there are no two distinct edges which have the same tail and the same
head. Otherwise we call G a multi digraph.
A path P in a digraph G is determined by a sequence (v1 , . . . , v` ) of vertices such that
vi 6= vj for all 1 ≤ i < j ≤ ` and (vi , vi+1 ) ∈ E(G) for all 1 ≤ i < `. We write E(P ) for the
set {(vi , vi+1 ) : 1 ≤ i ≤ ` − 1} of edges appearing in P and V (P ) for the set {v1 , . . . , v` } of
vertices. We say that P links v1 to v` .
Two paths P1 and P2 are edge disjoint if E(P1 ) ∩ E(P2 ) = ∅.

3

A polynomial-time algorithm on acyclic digraphs

In this section we prove the first main result of this paper, Theorem 3, which we repeat here
for convenience.
Theorem 3. For every fixed d ≥ 1, the (k, k − d)-Congestion Routing problem on
acyclic digraphs can be solved in time nO(d) .
We first need some additional notation and prove some auxiliary lemmas.
I Definition 5. Let G be a digraph and let L be a set of paths in G. For every v ∈ V (G)
we define the congestion of v with respect to L as the number of paths in L containing v.
The following lemma provides a simple extension of the algorithm from [15] for disjoint
paths in acyclic digraphs.
I Lemma 6. On acyclic digraphs G the (k, c)-Congestion Routing probem can be solved
in time nO(k) , where n := |G|.
Proof. In [15], Fortune et al. proved that the k-disjoint paths problem can be solved in time
nO(k) on any n-vertex acyclic digraph G.
Let G, (s1 , t1 ), . . . , (sk , tk ) and c be given. We construct a new digraph H with V (H) :=
V (G) × {1, . . . , c} and E(H) := { (u, i), (v, j) : (u, v) ∈ E(G)}.
Then H contains k pairwise vertex disjoint paths P1 , . . . , Pk such that Pi links (si , 1) to
(ti , 1) if, and only if, there is a positive solution to the (k, c)-Congestion Routing Problem

XX:3

XX:4

Routing with Congestion in Acyclic Digraphs

on G. By the algorithm in [15] we can decide whether the paths P1 , . . . , Pk exist in H in
time |V (H)|O(k) and hence in time (c · n)O(k) = nO(k) as c ≤ n.
J
We will use this lemma in the form given in the next corollary.
I Corollary 7. For c, k ≥ 0 such that k ∈ O(c), the (k, c)-Congestion Routing problem
can be solved on any acyclic n-vertex digraph G in time nO(c) .
The next lemma provides the main reduction argument for proving Theorem 3.
I Lemma 8. Let G be an acyclic directed graph and let d ≥ 1 and k > 3d. Let I :=
{(s1 , t1 ), . . . , (sk , tk )} ⊆ V (G) × V (G) be a set of source/terminal pairs. There exists a
(k−d)-routing of I if, and only if, for every pair (s, t) ∈ I there is a path in G from s to t
and there is a subset I 0 ( I of order |I 0 | = k − 1 such that there is a (k − d − 1)-routing of I 0 .
Proof. The if direction is easy to see. Let S 0 := {P1 , . . . , Pk−1 } be a (k − d − 1)-routing of a
set I 0 ⊆ I of order k − 1. Let s, t be such that I = I 0 ∪ {(s, t)}. By assumption there is a
simple path P from s to t in G. Then S := S 0 ∪ {P } is a (k − d)-routing of I.
For the reverse direction let I := {(s1 , t1 ), . . . , (sk , tk )} and let Ŝ := {P̂1 , . . . , P̂k } be a
(k − d)-routing of I such that P̂i links si to ti , for all 1 ≤ i ≤ k. We define a multi digraph
G0 on the same vertex set V (G) as G as follows. For every pair u, v ∈ V (G0 ) such that
e = (u, v) ∈ E(G) and every 1 ≤ i ≤ k, if e occurs on the path P̂i ∈ S, then we add a new
edge ei = (u, v) to G0 . Hence, if any edge e ∈ E(G) is used by ` different paths in Ŝ, then
G0 contains ` parallel edges between the endpoints of e. In the rest of the proof we will work
on the multi digraph G0 . We can now take a set S := {P1 , . . . , Pk } of pairwise edge disjoint
paths, where Pi is the path from si to ti induced by the edge set {ei : e ∈ E(P̂i )}. That is,
by using the parallel edges, we can turn the routing Ŝ into a (k−d)-routing S of I where the
paths are mutually edge disjoint.
In the remainder of the proof we will construct a subset I 0 ( I of order k − 1 and a
(k − d − 1)-routing of I 0 in G0 which is pairwise edge disjoint. This naturally induces a
(k − d − 1)-routing of I 0 in G. Note that in G0 , if L is any set of pairwise edge disjoint paths,
then the congestion of any vertex with respect to L is at most the congestion of the vertex
with respect to S (and thus Ŝ) in G0 (and G, respectively).
Let v be a topological ordering of G0 and let A := {a1 , . . . , a` } be the set of vertices of
congestion k − d with respect to S such that ai v aj whenever i < j. As k > 3d, for all
1 ≤ i < ` there is a path in G from ai to ai+1 .
For 1 ≤ i ≤ k, an atomic subpath of Pi (with respect to S) is a subpath of Pi that starts
and ends in a vertex of A ∪ {si , ti } and is internally vertex disjoint from A. Hence, every
path Pi ∈ S consists of the concatenation P11 · · · · · Pi`i of its atomic subpaths where we
identify the last vertex of Pij with the first vertex of Pij+1 for all 1 ≤ j < `i . Note that any
two atomic subpaths of paths Pi , Pj in S are pairwise edge disjoint.
0
} of I 0 is conservative
Let I 0 ⊂ I be a subset of order k − 1. A routing S 0 := {P10 , . . . , Pk−1
with respect to S if it consists of pairwise edge disjoint paths and every path in S 0 consists of
a concatenation of atomic subpaths of paths in S. In the sequel, whenever we speak of a
conservative I 0 -routing we implicitly mean that it is conservative with respect to S.
If S 0 is a conservative I 0 -routing with respect to S, then it consists of pairwise edge
disjoint paths and hence for every v ∈ V (G) the congestion of v with respect to S 0 is at most
the congestion of v with respect to S.
Let 1 ≤ i1 < i2 ≤ ` and let 1 ≤ j ≤ k. Let S 0 be a conservative I 0 -routing. An (i1 , i2 )jump of colour j is a subpath P 0 of Pj from ai1 to ai2 such that for all i with i1 < i < i2 the

Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, Roman Rabinovich

vertex ai is not on Pj . Note that any jump is an atomic subpath. We call the jump P 0 free
with respect to S 0 if P 0 is not used by any path in S 0 .
We are now ready to complete the proof of the lemma. Note first that, as k > 3d,
for any three vertices b1 , b2 , b3 ∈ A there is a path P ∈ S that contains b1 , b2 , b3 . Hence,
we can choose an h ∈ {1, . . . , k} such that a1 , a` ∈ V (Ph ) and there is a vertex ar with
1 < r < ` such that ar ∈ V (Ph ). Let I 0 := I \ {(sh , th )}. If A ⊆ V (Ph ), then S \ {Ph } is a
(k − d − 1)-routing of I 0 and we are done. Otherwise, for every vertex ar ∈ A which has
congestion k − d with respect to S \ {Ph } there are i, j with i < r < j and an (i, j)-jump
P of colour h. This follows as a1 , a` ∈ V (Ph ). Note also that a1 and a` have congestion
k − d − 1 in S \ {Ph }. Note that this jump P is free with respect to S \ {Ph }.
Thus, it is easily seen that S \ {Ph } satisfies the following two properties:
1. For every vertex ar of congestion k − d with respect to S \ {Ph } there are indices i < r < j
such that there is a free (i, j)-jump P with respect to S \ {Ph }.
2. For any three vertices b1 , b2 , b3 of congestion k − d with respect to S \ {Ph } there is a
path Q ∈ S \ {Ph } with {b1 , b2 , b3 } ⊆ V (Q).
Now let S 0 be a routing of I 0 which satisfies Condition 1 and 2 (with respect to S 0 instead
of S \ {Ph }) and, subject to this, the number of vertices of congestion k − d with respect to
S 0 is minimal.
We claim that S 0 is a (k − d − 1)-routing of I 0 . Let S 0 := {Q1 , . . . , Qk−1 }. Towards a
contradiction, suppose there is a vertex ar of congestion k − d with respect to S 0 . As S 0
is conservative, we have ar ∈ A. Hence, by assumption, there are i < r < j and a free
(i, j)-jump P with respect to S 0 .
Let Qh be a path in S 0 that contains ai , ar and aj , which exists by Condition 2. Let
Qh := Q1h ∪ Q2h ∪ Q3h where
Q1h is the initial subpath of Qh from its first vertex to ai ,
Q2h is the subpath starting at ai and ending in aj and
Q3h is the subpath starting in aj and ending at the end of Qh .
We define Q0h := Q1h ∪ P ∪ Q2h , i.e. Q0h is the path obtained from Qh by replacing the
inner subpath Q2h by the (i, j)-jump P . Let L := (S 0 \ {Qh }) ∪ {Q0h }. Then L is a routing of
I 0 . It is also conservative as we have only rerouted a single path along a free jump.
We need to show that for all b1 , b2 , b3 of congestion k − d with respect to L there is a
path Q ∈ L containing b1 , b2 , b3 . By assumption, such a path Q0 exists in S 0 . If Q0 =
6 Qh ,
then we are done. So suppose Qh = Q0 . But then this implies that bs 6∈ {ai+1 , . . . , aj−1 } for
all 1 ≤ s ≤ 3 as otherwise the congestion of bs would have dropped to k − d − 1 in L. But
then b1 , b2 , b3 ∈ V (Q0h ).
It remains to show that for every vertex as of congestion k − d with respect to L there is
a free (i, j)-jump for some i < s < j. As before, by assumption, there are s1 < s < s2 and a
free (s1 , s2 )-jump with respect to S 0 . If this jump is not P , then it still exists with respect to
L and we are done. So suppose this jump is P , which implies that i < s < j. Furthermore,
as 6∈ Qh as otherwise the congestion of as in L would be k − d − 1. But then, there must
be indices i1 , i2 with i ≤ i1 < s < i2 ≤ j such that ai1 , ai2 ∈ V (Qh ) and as0 6∈ V (Qh ) for
all i1 < s0 < i2 . Hence, the atomic subpath Q00 of Qh from ai1 to ai2 is an (i1 , i2 )-jump as
required. As Q00 ⊆ Q2h , this jump is now free.
Finally, the vertex ar now has congestion k − d − 1 with respect to L as ar is not contained
in Q0h . Hence, L has fewer vertices of congestion k − d than S 0 , contradicting the choice of
S 0 . Thus, S 0 must have been a (k − d − 1)-routing of I 0 as required. This completes the
proof of the lemma.
J

XX:5

XX:6

Routing with Congestion in Acyclic Digraphs

The previous lemma has the following consequene which essentially implies Theorem 3.
I Corollary 9. Let G be an acyclic digraph, let d ≥ 0 and let I := {(s1 , t1 ), . . . , (sk , tk )} be a
set of pairs of vertices such that for all 1 ≤ i ≤ k there is a path in G linking si to ti . G
contains a (k − d)-routing of I if, and only if, there is a subset I 0 ⊆ I of order |I 0 | ≤ 3d such
that G contains a (k−dc)-routing of I 0 . If k ≥ 3d, then I 0 can be chosen of size exactly 3d.
We are now ready to prove Theorem 3.
Proof of Theorem 3. Let G, k, d and I := {(s1 , t1 ), . . . , (sk , tk )} be given. Let n := |G|. If
for some 1 ≤ i ≤ k there is no path in G from si to ti , then the answer is no and we are done.
If k ≤ 3d, then we can apply Corollary 7 to compute the answer in time nO(d) as required.
Otherwise, by Corollary 9, there is a (k − d)-routing for I in G if, and only
is a
 if, there
k
0
0
3d
subset I ( I of order 3d such that I has a (3d − d)-routing. There are 3d ≤ k ≤ n3d
subsets I 0 of order 3d. By Corollary 7, we can decide for any such I 0 of order 3d in time
nO(d) whether a (3d − d)-routing of I 0 exists. Hence, by iterating through all possible subsets
I 0 , we can decide in time nO(d) whether there is a (k − d)-routing of I in G.
J

4

Lower Bounds

In this section, we prove Theorem 2 by a reduction from Partitioned Subgraph Isomorphism. The input of the Partitioned Subgraph Isomorphism problem consists of a
graph H with vertex set {u1 , . . . , uk } and a graph G whose vertex set is partitioned into k
classes V1 , . . . , Vk . The task is to find a mapping µ : V (H) → V (G) such that µ(ui ) ∈ Vi for
every 1 ≤ i ≤ k and µ is a subgraph embedding, that is, if ui and uj are adjacent in H, then
µ(ui ) and µ(uj ) are adjacent in G.
I Theorem 10 ([20]). Assuming ETH, Partitioned Subgraph Isomorphism cannot be
solved in time f (k)no(k/ log k) (where k = |V (H)|) for any computable function f , even when
H is assumed to be 3-regular and bipartite.
To prove Theorem 2, we need a reduction from Partitioned Subgraph Isomorphism
(for 3-regular bipartite graphs) to (k, c)-Congestion Routing, where the number k of
demands is linear in the number of vertics of H.
Proof (of Theorem 2). We prove the theorem by a reduction from Partitioned Subgraph
Isomorphism. Let H and G be two graphs, let V (H) = {u1 , . . . , uk }, and let (V1 , . . . , Vk )
be a partition of V (G). By copying vertices if necessary, we may assume that every Vi has
the same size n; let us denote by {vi,1 , . . . , vi,n } the vertices in Vi . By Theorem 10, we may
assume that H is 3-regular and bipartite. This means that H has exactly h = 3k/2 edges
and both partite classes contain k/2 vertices. Without loss of generality, we can assume
that U1 = {u1 , . . . , uk/2 } and U2 = {uk/2+1 , . . . , uk } are the two partite classes. Let us fix
an arbitrary ordering e1 , . . . , eh of the edges of H.
Construction. We construct an instance of (k, c)-Congestion Routing the following way.
We construct a directed graph D that contains, for every 1 ≤ i ≤ k, two directed paths
Qi and Qi (see Figure 1). Path Qi has n(h + 1) + 1 vertices: it contains the vertices q i,0 ,
. . . , q i,n in this order and additionally, for every 1 ≤ j ≤ n, the vertices q i,j,1 , . . . , q i,j,h
are inserted between q i,j−1 and q i,j . The path Qi is defined the same way, with vertices q
instead of q. For every 1 ≤ ` ≤ h, we introduce two vertices s` and t` . Then we complete
the construction of the graph D by introducing further edges as follows.

Saeed Akhoondian Amiri, Stephan Kreutzer, Dániel Marx, Roman Rabinovich
s1
q 1,1,1
Q1
Q1

q 1,1,6

s2

s3

s4

q 1,2,1

...

sh

q 1,3,4

q 1,0

q 1,1

q 1,2

q 1,0

q 1,1

q 1,2

q 1,3

q 1,4

q 1,5

q 1,3

q 1,4

q 1,5

q 1,3,4

Q2
Q2
Q3
Q3

XX:7

q 3,5,4
q 3,0

q 3,1

q 3,2

q 3,3

q 3,4

q 3,0

q 3,1

q 3,2

q 3,3

q 3,4

q 3,5

q 3,5
q 3,5,4

Q4
Q4

t1

t2

t3

t4

...

th

Figure 1 Part of the directed graph D constructed in the proof of Theorem 2 with k = 4, h = 6,
and n = 5. For clarity, we consider only one edge e4 of H, which connects u1 and u3 , and assume
that the only edge between V1 and V3 is between v1,3 and v3,5 . The highlighted red paths show the
paths P1v , P3v , and P4e of the solution.

For every 1 ≤ i ≤ k and 1 ≤ j ≤ n, we introduce the edge (q i,j−1 , q i,j ) (the curved bypass
edges in Figure 1).
For every 1 ≤ i ≤ k, 1 ≤ j ≤ n, and 1 ≤ s ≤ h, we introduce the edge (q i,j,s , q i,j,s ) (the
vertical edges in Figure 1).
For every 1 ≤ ` ≤ h, we do the following. Suppose that edge e` of H connects uia and uib
for some 1 ≤ ia ≤ k/2 and k/2 + 1 ≤ ib ≤ k. Then for every pair of vertices via ,ja ∈ Via
and vib ,jb ∈ Vib that are adjacent in G, we introduce the following three edges into D:
(s` , q ia ,ja ,` ), (q i ,j ,` , q ib ,jb ,` ), and (q i ,j ,` , t` ).
a a
b b
To complete the construction of the (k, c)-Congestion Routing instance, we define the following
set of k + 2k(c − 1) + h demands:
For every 1 ≤ i ≤ k, we introduce the demand (q i,0 , q i,n ) (vertex demands).
For every 1 ≤ i ≤ k, we introduce c − 1 copies of the demand (q i,0 , q i,n ) (blocking
demands).
For every 1 ≤ i ≤ k, we introduce c − 1 copies of the demand (q i,0 , q i,n ) (blocking
demands).
For every 1 ≤ ` ≤ h, we introduce the demand (s` , t` ) (edge demands).
Note that, for every fixed c ≥ 1, the number of demands is O(k). In the rest of the proof,

XX:8

Routing with Congestion in Acyclic Digraphs

we show that a routing with congestion c exists if and only if the Partitioned Subgraph
Isomorphism instance has a solution. Then the W[1]-hardness and lower bound stated in
Theorem 10 implies the same hardness results for the routing problem.
Subgraph embedding ⇒ routing. Suppose first that vertices v1,z1 ∈ V1 , . . . , vk,zk ∈
Vk form a solution to the Partitioned Subgraph Isomorphism instance. We construct a
routing that contains the following paths, satisfying the demands defined above:
For every 1 ≤ i ≤ k, the vertex demand (q i,0 , q i,n ) is satisfied by a path Piv that goes
from q i,0 to q i,zi −1 on Qi , uses the edge (q i,zi −1 , q i,z ), and the goes from q i,z to q i,n on
i
i
Qi .
For every 1 ≤ i ≤ k, each of the c − 1 copies of the blocking demand (q i,0 , q i,n ) is satisfied
by a path going on Qi .
For every 1 ≤ i ≤ k, each of the c − 1 copies of the blocking demand (q i,0 , q i,n ) is satisfied
by a path going on Qi .
For every 1 ≤ ` ≤ h, the edge demand (s` , t` ) is satisfied by a 5-edge path P`e =
(s` , q ia ,zia ,` , q i ,z ,` , q ib ,zi ,` , q i ,z ,` , t` ).
a

ib

b

b

ib

It is easy to verify that these are indeed paths: all the required edges exist. We claim that
each vertex of D is used by at most c of these paths. It is easy to see that two paths Piv0
and Piv00 with i 6= i00 satisfying vertex demands do intersect, and this is also true for any two
paths P`e0 and P`e00 with `0 6= `00 satisfying edge demands (note that each vertex of the path
P`e has ` in its index). The crucial observation is that the path Piv does intersect the path
P`e for any `. The only way this could possibly happen is if edge e` of H connects uia with
uib , and i is equal to ia or ib . But the path P`e uses only vertex q ia ,zia ,` from Qia and vertex
q i ,z ,` from Qi , while the path Piv does not use these vertices, as it jumps from q i,zi −1 to
a

ib

b

q i,z . Thus each vertex is used by at most c − 1 paths satisfying a blocking demand and at
i
most one additional path satisfying a vertex or edge demand. We can conclude that each
vertex is used by at most c of the paths, what we had to show.
Routing ⇒ subgraph embedding. Next we show that given a routing with congestion
c, it is possible to construct the required subgraph embedding from H to G. It is clear that
the path satisfying the blocking demand (q i,0 , q i,n ) is exactly Qi : after leaving Qi , there is no
way to return back to it. Similarly, the solution must use path Qi to satisfying the blocking
demand (q i,0 , q i,n ). It is also clear that the path Piv satisfying the vertex demand (q i,0 , q i,n )
has to be contained in the union of Qi and Qi . Let 1 ≤ zi ≤ n be the smallest value such
that q i,z is on path Piv (note that this value is positive, as vertex q i,0 cannot be reached
i
from q i,0 ). Observe that path Piv uses every vertex of Qi from q i,z to q i,n (as it cannot leave
i
Qi ). Moreover, since Piv does not use the part of Qi from q i,0 to q i,z −1 by definition, it has
i

to use the part of Qi from q i,0 to q i,zi −1 .
We claim that mapping vertex ui of H to vertex vi,zi of G is a correct subgraph embedding
of H into G. To show this, suppose that edge ei of H connects uia and uib with 1 ≤ ia ≤ k/2
and k/2 + 1 ≤ ib ≤ k; we need to show that via ,zia ∈ Via and vib ,zib ∈ Vib are adjacent.
Consider the path P`e satisfying edge demand (s` , t` ). By construction, the vertex of P`e after
s` has to be on the path Qia and the vertex of P`e before t` has to be on Qi . The only way
b

to go from Qia to Qi is to use an edge of the form (q i
b

a ,ja

): the only way we can
,q
,` ib ,jb ,`

leave the union of Qia and Qi is to enter some Qi with k/2 + 1 ≤ i ≤ k, and there is no
a

edge connecting Qib or Qi with any Qi with k/2 + 1 ≤ i ≤ k and i 6= ib (this is the part
b
of the proof where we use that H is bipartite). We claim that ja = zia . If j > zia , then
q i ,j ,` is also used by the c − 1 paths satisfying the blocking demand (q i ,0 , q i ,n ) and (as we
a

a

a

a

REFERENCES

XX:9

have seen) the path Piva , contradicting the assumption that the routing has congestion c. If
j < zia , then there is no way for the path P`e to reach q i ,j ,` from s` : each vertex of the path
a

a

Qia from q ia ,0 to q ia ,ja is used by c − 1 paths satisfying the blocking demand (q i ,0 , q i ,n )
a
a
and (as shown above) by the path Piva . This shows jz = zia and a similar argument shows
jb = zib . Now the existence of the edge (q i ,z ,` , q ib ,zb ,` ) means, by construction, that G
a a
contains an edge between via ,za ∈ Via and vib ,zb ∈ Vib , what we had to show.
J

5

Conclusion

In this paper we have studied the (k, c)-Congestion Routing problem on acyclic digraphs.
It is easy to see that the nO(k) algorithm in [15] for solving the disjoint paths problem on
acyclic digraphs can be extended to an nO(k) algorithm for (k, c)-Congestion Routing.
As we proved in Theorem 2, the nO(k) time algorithm is essentially best possible with respect
to the exponent of n, under the Exponential-Time Hypothesis (ETH). We therefore studied
the extreme cases of relatively high congestion k − d for some fixed value of d. In Theorem 3
we showed that in this case we can obtain an nO(d) algorithm on acyclic digraphs, i.e. the
algorithm only depends on the offset d in (k, k − d)-Congestion Routing but not on the
number k of demand pairs. The proof relied on a reduction argument that shows that as long
as k is big enough compared to d, then a demand pair can be eliminated without changing
the answer.
It will be interesting to see whether our result can be extended to larger classes of digraphs.
In particular classes of digraphs of bounded directed tree width would be a natural target.
On such classes, the k-disjoint paths problem can be solved in time nO(k+w) , where w is the
directed tree width of the input digraph (see [17]). It is conceivable that our results extend
to bounded directed tree width classes and we leave this for future research.

References
1 Saeed Akhoondian Amiri, Ali Golshani, Stephan Kreutzer, and Sebastian Siebertz. Vertex
disjoint paths in upward planar graphs. In Edward A. Hirsch, Sergei O. Kuznetsov,
Jean-Éric Pin, and Nikolay K. Vereshchagin, editors, Computer Science - Theory and
Applications: 9th International Computer Science Symposium in Russia, CSR 2014,
Moscow, Russia, June 7-11, 2014. Proceedings, pages 52–64. Springer International
Publishing, Cham, 2014. URL: http://dx.doi.org/10.1007/978-3-319-06686-8_5,
doi:10.1007/978-3-319-06686-8_5.
2 Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal
Talwar, and Lisa Zhang. Inapproximability of edge-disjoint paths and low congestion
routing on undirected graphs. Combinatorica, 30(5):485–520, 2011. URL: http://dx.
doi.org/10.1007/s00493-010-2455-9, doi:10.1007/s00493-010-2455-9.
3 Jorgen Bang-Jensen and Gregory Z. Gutin. Digraphs - Theory, Algorithms and Applications. Springer, 2nd edition, 2010.
4 Parinya Chalermsook, Julia Chuzhoy, Alina Ene, and Shi Li. Approximation algorithms
and hardness of integral concurrent flow. In Proceedings of the Forty-fourth Annual ACM
Symposium on Theory of Computing, STOC ’12, pages 689–708, New York, NY, USA,
2012. ACM. URL: http://doi.acm.org/10.1145/2213977.2214040, doi:10.1145/
2213977.2214040.
5 C. Chekuri, S. Khanna, and F. B. Shepherd. Edge-disjoint paths in planar graphs. In

XX:10

REFERENCES

6

7

8

9

10

11

12

13
14
15

16
17
18

Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on,
pages 71–80, Oct 2004. doi:10.1109/FOCS.2004.27.
Chandra Chekuri and Alina Ene. Poly-logarithmic approximation for maximum node
disjoint paths with constant congestion. In Sanjeev Khanna, editor, Proceedings of the
Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New
Orleans, Louisiana, USA, January 6-8, 2013, pages 326–341. SIAM, 2013. URL: http:
//dx.doi.org/10.1137/1.9781611973105.24, doi:10.1137/1.9781611973105.24.
Chandra Chekuri and Alina Ene. The all-or-nothing flow problem in directed graphs
with symmetric demand pairs. In Jon Lee and Jens Vygen, editors, Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014,
Bonn, Germany, June 23-25, 2014. Proceedings, volume 8494 of Lecture Notes in Computer Science, pages 222–233. Springer, 2014. URL: http://dx.doi.org/10.1007/
978-3-319-07557-0_19, doi:10.1007/978-3-319-07557-0_19.
Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. Multicommodity flow,
well-linked terminals, and routing problems. In Proceedings of the Thirty-seventh Annual
ACM Symposium on Theory of Computing, STOC ’05, pages 183–192, New York, NY,
USA, 2005. ACM. URL: http://doi.acm.org/10.1145/1060590.1060618, doi:10.
1145/1060590.1060618.
√
Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. An o( n) approximation
and integrality gap for disjoint paths and unsplittable flow. Theory of Computing,
2(7):137–146, 2006. URL: http://www.theoryofcomputing.org/articles/v002a007,
doi:10.4086/toc.2006.v002a007.
J. Chuzhoy and S. Li. A polylogarithmic approximation algorithm for edge-disjoint paths
with congestion 2. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual
Symposium on, pages 233–242, Oct 2012. doi:10.1109/FOCS.2012.54.
M. Cygan, D. Marx, M. Pilipczuk, and M. Pilipczuk. The planar directed k-vertex-disjoint
paths problem is fixed-parameter tractable. In Foundations of Computer Science (FOCS),
2013 IEEE 54th Annual Symposium on, pages 197–206, Oct 2013. doi:10.1109/FOCS.
2013.29.
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx,
Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms.
Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21275-3, doi:10.
1007/978-3-319-21275-3.
Reinhard Diestel. Graph Theory. Springer-Verlag, 4th edition, 2010.
S. Even, A. Itai, and A. Shamir. On the complexity of timetable and multicommodity
flow problems. SIAM J. Comput., 5(4):691–703, 1976.
Steven Fortune, John Hopcroft, and James Wyllie. The directed subgraph homeomorphism
problem. Theoretical Computer Science, 10(2):111 – 121, 1980. URL: http://www.
sciencedirect.com/science/article/pii/0304397580900092, doi:http://dx.doi.
org/10.1016/0304-3975(80)90009-2.
Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have
strongly exponential complexity? J. Comput. System Sci., 63(4):512–530, 2001.
Thor Johnson, Neil Robertson, Paul D. Seymour, and Robin Thomas. Directed tree-width.
J. Comb. Theory, Ser. B, 82(1):138–154, 2001.
G. Stavros Kolliopoulos and Clifford Stein. Approximating disjoint-path problems using
packing integer programs. Mathematical Programming, 99(1):63–87, 2003. URL: http:
//dx.doi.org/10.1007/s10107-002-0370-6, doi:10.1007/s10107-002-0370-6.

REFERENCES

19 Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. Lower bounds based on the
exponential time hypothesis. Bulletin of the EATCS, 105:41–72, 2011. URL: http:
//albcom.lsi.upc.edu/ojs/index.php/beatcs/article/view/96.
20 Dániel Marx. Can you beat treewidth? Theory of Computing, 6(1):85–112, 2010.
arXiv:toc:v006/a005, doi:10.4086/toc.2010.v006a005.
21 N. Robertson and P. D. Seymour. Graph minors I – XXIII, 1982 – 2010. Appearing in
Journal of Combinatorial Theory, Series B., from 1982-2010.
22 Aleksandrs Slivkins. Parameterized tractability of edge-disjoint paths on directed acyclic
graphs. SIAM J. Discrete Math., 24(1):146–157, 2010. URL: http://dx.doi.org/10.
1137/070697781, doi:10.1137/070697781.

XX:11

