Almost Polynomial Hardness of Node-Disjoint Paths in Grids
Julia Chuzhoy∗

David H. K. Kim†

Rachit Nimavat‡

arXiv:1711.01980v1 [] 6 Nov 2017

November 7, 2017

Abstract
In the classical Node-Disjoint Paths (NDP) problem, we are given an n-vertex graph G = (V, E),
and a collection M = {(s1 , t1 ), . . . , (sk , tk )} of pairs of its vertices, called source-destination, or
demand pairs. The goal is to route as many of the demand pairs as possible, where to route a pair
we need to select a path connecting it, so that all
√ selected paths are disjoint in their vertices. The
best current algorithm for NDP achieves an O( n)-approximation, while, until recently, the best
negative result was a factor Ω(log1/2− n)-hardness of approximation, for any constant , √unless
NP ⊆ ZPTIME(npoly log n ). In a recent work, the authors have shown an improved 2Ω( log n) hardness of approximation for NDP, unless NP ⊆ DTIME(nO(log n) ), even if the underlying graph is
a subgraph of a grid graph, and all source vertices lie on the boundary of the grid. Unfortunately,
this result does not extend to grid graphs.
The approximability of the NDP problem on grid graphs has remained a tantalizing open question, with the best current upper bound of Õ(n1/4 ), √
and the best current lower bound of APXÕ( log n)
hardness. In a recent work, the authors showed a 2
-approximation algorithm for NDP in
grid graphs, if all source vertices lie on the boundary of the grid – a result that can be seen as suggesting that a sub-polynomial approximation may be achievable for NDP in grids. In this paper we
show that this is unlikely to be the case, and come close to resolving the approximability of NDP in
1−
general, and NDP in grids in particular. Our main result is that NDP is 2Ω(log n) -hard to approxi2
mate for any constant , assuming that NP * RTIME(npoly log n ), and that it is nΩ(1/(log log n) ) -hard
δ
to approximate, assuming that for some constant δ > 0, NP 6⊆ RTIME(2n ). These results hold even
for grid graphs and wall graphs, and extend to the closely related Edge-Disjoint Paths problem,
even in wall graphs.
Our hardness proof performs a reduction from the 3COL(5) problem to NDP, using a new graph
partitioning problem as a proxy. Unlike the more standard approach of employing Karp reductions
to prove hardness of approximation, our proof is a Cook-type reduction, where, given an input
instance of 3COL(5), we produce a large number of instances of NDP, and apply an approximation
algorithm for NDP to each of them. The construction of each new instance of NDP crucially depends
on the solutions to the previous instances that were found by the approximation algorithm.

∗
Toyota Technological Institute at Chicago. Email: cjulia@ttic.edu. Supported in part by NSF grants CCF-1318242
and CCF-1616584.
†
Computer Science Department, University of Chicago. Email: hongk@cs.uchicago.edu. Supported in part by NSF
grant CCF-1318242 and CCF-1616584.
‡
Toyota Technological Institute at Chicago. Email: nimavat@ttic.edu. Supported in part by NSF grant CCF1318242.

1

Introduction

We study the Node-Disjoint Paths (NDP) problem: given an undirected n-vertex graph G and a
collection M = {(s1 , t1 ), . . . , (sk , tk )} of pairs of its vertices, called source-destination, or demand
pairs, we are interested in routing the demand pairs, where in order to route a pair (si , ti ), we need
to select a path connecting si to ti . The goal is to route as many of the pairs as possible, subject to
the constraint that the selected routing paths are mutually disjoint in their vertices and their edges.
We let S = {s1 , . . . , sk } be the set of the source vertices, T = {t1 , . . . , tk } the set of the destination
vertices, and we refer to the vertices of S ∪ T as terminals. We denote by NDP-Planar the special case
of the problem where the graph G is planar; by NDP-Grid the special case where G is a square grid;
and by NDP-Wall the special case where G is a wall (see Figure 1 for an illustration of a wall and
Section 2 for its formal definition).
NDP is a fundamental problem in the area of graph routing, that has been studied extensively. Robertson and Seymour [RS90, RS95] showed, as part of their famous Graph Minors Series, an efficient algorithm for solving the problem if the number k of the demand pairs is bounded by a constant. However,
when k is a part of the input, the problem becomes NP-hard [Kar75, EIS76], and it remains NP-hard
even for planar graphs [Lyn75], and for grid graphs [KvL84]. The best current upper bound on the
√
approximability of NDP is O( n), obtained by a simple greedy algorithm [KS04]. Until recently, the
best known lower bound was an Ω(log1/2− n)-hardness of approximation for any constant , unless
NP ⊆ ZPTIME(npoly log n ) [AZ05, ACG+ 10], and APX-hardness for the special cases of NDP-Planar
√
and NDP-Grid [CK15]. In a recent paper [CKN17b], the authors have shown an improved 2Ω( log n) hardness of approximation for NDP, assuming that NP * DTIME(nO(log n) ). This result holds even for
planar graphs with maximum vertex degree 3, where all source vertices lie on the boundary of a single
face, and for sub-graphs of grid graphs, with all source vertices lying on the boundary of the grid.
√
We note that for general planar graphs, the O( n)-approximation algorithm of [KS04] was recently
slightly improved to an Õ(n9/19 )-approximation [CKL16].
The approximability status of NDP-Grid— the special case of NDP where the underlying graph is a
square grid — remained a tantalizing open question. The study of this problem dates back to the
70’s, and was initially motivated by applications to VLSI design. As grid graphs are extremely wellstructured, one would expect that good approximation algorithms can be designed for them, or that, at
the very least, they should be easy to understand. However, establishing the approximability of NDP√
Grid has been elusive so far. The simple greedy O( n)-approximation algorithm of [KS04] was only
recently improved to a Õ(n1/4 )-approximation for NDP-Grid [CK15], while on the negative
side only
√
APX-hardness is known. In a very recent paper [CKN17a], the authors designed a 2O( log n·log log n )approximation algorithm for a special case of NDP-Grid, where
√ the source vertices appear on the grid
Ω(
log n) -hardness of approximation of NDP
boundary. This result can be seen as complementing the 2
on sub-graphs of grids with all sources lying on the grid boundary [CKN17b]1 . Furthermore, this
result can be seen as suggesting that sub-polynomial approximation algorithms may be achievable for
NDP-Grid.
In this paper we show that this is unlikely to be the case, and come close to resolving the approximabil1−
ity status of NDP-Grid, and of NDP in general, by showing that NDP-Grid is 2Ω(log n) -hard to approxi2
mate for any constant , unless NP ⊆ RTIME(npoly log n ). We further show that it is nΩ(1/(log log n) ) -hard
δ
to approximate, assuming that for some constant δ > 0, NP 6⊆ RTIME(2n ). The same hardness results
also extend to NDP-Wall. These hardness results are stronger than the √best currently known hardness for the general NDP problem, and should be contrasted with the 2O( log n·log log n )-approximation
1

Note that the results are not strictly complementary: the algorithm only works on grid graphs, while the hardness
result is only valid for sub-graphs of grids.

1

algorithm for NDP-Grid with all sources lying on the grid boundary [CKN17a].
Another basic routing problem that is closely related to NDP is Edge-Disjoint Paths (EDP). The
input to this problem is the same as before: an undirected graph G = (V, E) and a set M =
{(s1 , t1 ), . . . , (sk , tk )} of demand pairs. The goal, as before, is to route the largest number of the
demand pairs via paths. However, we now allow the paths to share vertices, and only require that
they are mutually edge-disjoint. In general, it is easy to see that EDP is a special case of NDP. Indeed,
given an EDP instance (G, M), computing the line graph of the input graph G transforms it into
an equivalent instance of NDP. However, this transformation may inflate the number of the graph
vertices, and so approximation factors that depend on |V (G)| may no longer be preserved. Moreover,
this transformation does not preserve planarity, and no such relationship is known between NDP and
EDP in planar graphs. The approximability status of EDP is very similar to that of NDP: the best
√
current
approximation algorithm achieves an O( n)-approximation factor [CKS06], and the recent
√
2Ω( log n) -hardness of approximation of [CKN17b], under the assumption that NP 6⊆ DTIME(nO(log n) ),
extends to EDP. Interestingly, EDP appears to be relatively easy on grid graphs, and has a constantfactor approximation for this special case [AR95, KT98, KT95]. The analogue of the grid graph in
the setting of EDP seems to be the wall graph (see Figure 1): the approximability status of EDP on
1/4 ),
wall graphs is similar to that of NDP on grid graphs, with the best current upper bound of Õ(n
√
and the best lower bound of APX-hardness [CK15]. The results of [CKN17b] extend to a 2Ω( log n) hardness of approximation for EDP on sub-graphs of wall graphs, with all source vertices lying on the
wall boundary, under the same complexity assumption. We denote by EDP-Wall the special case of
the EDP problem where the underlying graph is a wall. We show that our new almost polynomial
hardness of approximation results also hold for EDP-Wall and for NDP-Wall.

Figure 1: A wall graph.

Other Related Work. Several other special cases of EDP are known to have reasonably good approximation algorithms. For example, for the special case of Eulerian planar graphs, Kleinberg [Kle05]
showed an O(log2 n)-approximation algorithm, while Kawarabayashi and Kobayashi [KK13] provide
an improved O(log n)-approximation for both Eulerian and 4-connected planar graphs. Polylogarithmic approximation algorithms are also known for bounded-degree expander graphs [LR99, BFU92,
BFSU98, KR96, Fri00], and constant-factor approximation algorithms are known for trees [GVY97,
CMS07], and grids and grid-like graphs [AR95, AGLR94, KT98, KT95]. Rao and Zhou [RZ10] showed
an efficient randomized O(poly log n)-approximation algorithm for the special case of EDP where the
value of the global minimum cut in the input graph is Ω(log5 n). Recently, Fleszar et al. [FMS16]
√
designed an O( r · log1.5 (kr))-approximation algorithm for EDP, where r is the feedback vertex set
number of the input graph G = (V, E) — the smallest number of vertices that need to be deleted from
G in order to turn it into a forest.
A natural variation of NDP and EDP that relaxes the disjointness constraint by allowing a small
vertex- or edge-congestion has been a subject of extensive study. In the NDP with Congestion (NDPwC)
problem, the input consists of an undirected graph and a set of demand pairs as before, and additionally
a non-negative integer c. The goal is to route a maximum number of the demand pairs with congestion
2

c, that is, each vertex may participate in at most c paths in the solution. The EDP with Congestion
problem (EDPwC) is defined similarly, except that now the congestion is measured on the graph
edges and not vertices. The famous result of Raghavan and Thompson [RT87], that introduced the
randomized LP-rounding technique, obtained a constant-factor approximation for NDPwC and EDPwC,
for a congestion value c = Θ(log n/ log log n). A long sequence of work [CKS05, Räc02, And10, RZ10,
Chu16, CL16, CE13, CC] has led to an O(poly log k)-approximation for NDPwC and EDPwC with
congestion bound c = 2. This result is essentially optimal, since it is known that for every constant ,
and for every congestion value c = o(log log n/ log log log n), both problems are hard to approximate
1−
to within a factor Ω((log n) c+1 ), unless NP ⊆ ZPTIME(npoly log n ) [ACG+ 10]. When the input graph is
planar, Seguin-Charbonneau and Shepherd [SCS11], improving on the result of Chekuri, Khanna and
Shepherd [CKS09], have shown a constant-factor approximation for EDPwC with congestion 2.
Our Results and Techniques.

Our main result is the proof of the following two theorems.
1−

Theorem 1.1 For every constant  > 0, there is no 2O(log n) -approximation algorithm for NDP,
2
assuming that NP * RTIME(npoly log n ). Moreover, there is no nO(1/(log log n) ) -approximation algorithm
δ
for NDP, assuming that for some constant δ > 0, NP * RTIME(2n ). These results hold even when
the input graph is a grid graph or a wall graph.
1−

Theorem 1.2 For every constant  > 0, there is no 2O(log n) -approximation algorithm for EDP,
2
assuming that NP * RTIME(npoly log n ). Moreover, there is no nO(1/(log log n) ) -approximation algorithm
δ
for EDP, assuming that for some constant δ > 0, NP * RTIME(2n ). These results hold even when
the input graph is a wall graph.
We now provide a high-level overview of our techniques. The starting point of our hardness of approximation proof is 3COL(5) — a special case of the 3-coloring problem, where the underlying graph is
5-regular. We define a new graph partitioning problem, that we refer to as (r, h)-Graph Partitioning,
and denote by (r,h)-GP. In this problem, we are given a bipartite graph G̃ = (V1 , V2 , E) and two
integral parameters r, h > 0. A solution to the problem is a partition (W1 , W2 , . . . , Wr ) of V1 ∪ V2 into
r subsets, and
Pfor each 1 ≤ i ≤ r, a subset Ei ⊆ E(Wi ) of edges, so that |Ei | ≤ h holds, and the goal is
to maximize ri=1 |Ei |. A convenient intuitive way to think about this problem is that we would like to
partition G̃ into a large number of subgraphs, in a roughly balanced way (with respect to the number of
edges), so as to preserve as many of the edges as possible. We show that NDP-Grid is at least as hard as
the (r,h)-GP problem (to within polylogarithmic factors). Our reduction exploits the fact that routing
in grids is closely related to graph drawing, and that graphs with small crossing number have small
balanced separators. The (r,h)-GP problem itself appears similar in flavor to the Densest k-Subgraph
problem (DkS). In the DkS problem, we are given a graph G = (V, E) and a parameter k, and the goal
is to find a subset U ⊆ V of k vertices, that maximizes the number of edges in the induced graph G[U ].
Intuitively, in the (r,h)-GP problem, the goal is to partition the graph into many dense subgraphs,
and so in order to prove that (r,h)-GP is hard to approximate, it is natural to employ techniques
used in hardness of approximation proofs for DkS. The best current approximation algorithm for DkS
achieves a n1/4+ -approximation for any constant  [BCC+ 10]. Even though the problem appears to
be very hard to approximate, its hardness of approximation proof has been elusive until recently: only
constant-factor hardness results were known for DkS under various worst-case complexity assumptions,
2/3
and 2Ω(log n) -hardness under average-case assumptions [Fei02, AAM+ 11, Kho04, RS10]. In a recent
breakthrough, Manurangsi [Man17] has shown that for some constant c, DkS is hard to approximate to
c
within a factor n1/(log log n) , under the Exponential Time Hypothesis. Despite our feeling that (r,h)-GP
is somewhat similar to DkS, we were unable to extend the techniques of [Man17] to this problem, or
to prove its hardness of approximation via other techniques.
3

We overcome this difficulty as follows. First, we define a graph partitioning problem that is slightly
more general than (r,h)-GP. The definition of this problem is somewhat technical and is deferred to
Section 3. This problem is specifically designed so that the reduction to NDP-Grid still goes through,
but it is somewhat easier to control its solutions and prove hardness of approximation for it. Furthermore, instead of employing a standard Karp-type reduction (where an instance of 3COL(5) is
reduced to a single instance of NDP-Grid, while using the graph partitioning problem as a proxy),
we employ a sequential Cook-type reduction. We assume for contradiction that an α-approximation
algorithm A for NDP-Grid exists, where α is the hardness of approximation factor we are trying to
prove. Our reduction is iterative. In every iteration j, we reduce the 3COL(5) instance to a collection
Ij of instances of NDP-Grid, and apply the algorithm A to each of them. If the 3COL(5) instance is a
Yes-Instance, then we are guaranteed that each resulting instance of NDP-Grid has a large solution,
and so all solutions returned by A are large. If the 3COL(5) instance is a No-Instance, then unfortunately it is still possible that the resulting instances of NDP-Grid will have large solutions. However,
we can use these resulting solutions in order to further refine our reduction, and construct a new
collection Ij+1 of instances of NDP-Grid. While in the Yes-Instance case we will continue to obtain
large solutions to all NDP-Grid instances that we construct, we can show that in the No-Instance
case, in some iteration of the algorithm, we will fail to find such a large solution. Our reduction is
crucially sequential, and we exploit the solutions returned by algorithm A in previous iterations in
order to construct new instances of NDP-Grid for the subsequent iterations. It is interesting whether
these techniques may be helpful in obtaining new hardness of approximation results for DkS.
We note that our approach is completely different from the previous hardness of approximation proof
of [CKN17b]. The proof in [CKN17b] proceeded by performing a reduction from 3SAT(5). Initially, a
simple reduction from 3SAT(5) to the NDP problem on a sub-graph of the grid graph is used in order
to produce a constant hardness gap. The resulting instance of NDP is called a level-1 instance. The
reduction then employs a boosting technique, that, in order to obtain a level-i instance, combines a
number of level-(i − 1) instances with a single level-1 instance. The hardness gap grows by a constant
factor from iteration to iteration, until the desired hardness of approximation bound is achieved. All
source vertices in the constructed instances appear on the grid boundary, and a large number of vertices
are carefully removed from the grid in order to create obstructions to routing, and to force the routing
paths to behave in a prescribed way. The reduction itself is a Karp-type reduction, and eventually
produces a single instance of NDP with a large gap between the Yes-Instance and No-Instance
solutions.
Organization. We start with Preliminaries in Section 2, and introduce the new graph partitioning
problems in Section 3. The hardness of approximation proof for NDP-Grid appears in Section 4, with
the reduction from the graph partitioning problem to NDP-Grid deferred to Section 5. Finally, we
extend our hardness results to NDP-Wall and EDP-Wall in Section 6.

2

Preliminaries

We use standard graph-theoretic notation. Given a graph G and a subset W ⊆ V (G) of its vertices,
E(W ) denotes the set of all edges of G that have both their endpoints in W . Given a path P and a
subset U of vertices of G, we say that P is internally disjoint from U iff every vertex in P ∩ U is an
endpoint of P . Similarly, P is internally disjoint from a subgraph G0 of G iff P is internally disjoint
from V (G0 ). Given a subset M0 ⊆ M of the demand pairs in G, we denote by S(M0 ) and T (M0 )
the sets of the source and the destination vertices of the demand pairs in M0 , respectively. We let
T (M0 ) = S(M0 ) ∪ T (M0 ) denote the set of all terminals participating as a source or a destination in
4

M0 . All logarithms in this paper are to the base of 2.
Grid Graphs. For a pair h, ` > 0 of integers, we let Gh,` denote the grid of height h and length
`. The set of its vertices is V (Gh,` ) = {v(i, j) | 1 ≤ i ≤ h, 1 ≤ j ≤ `}, and the set of its edges is the
union of two subsets: the set E H = {(vi,j , vi,j+1 ) | 1 ≤ i ≤ h, 1 ≤ j < `} of horizontal edges and the
set E V = {(vi,j , vi+1,j ) | 1 ≤ i < h, 1 ≤ j ≤ `} of vertical edges. The subgraph of Gh,` induced by the
edges of E H consists of h paths, that we call the rows of the grid; for 1 ≤ i ≤ h, the ith row Ri is
the row containing the vertex v(i, 1). Similarly, the subgraph induced by the edges of E V consists of
` paths that we call the columns of the grid, and for 1 ≤ j ≤ `, the jth column Wj is the column
containing v(1, j). We think of the rows as ordered from top to bottom and the columns as ordered
from left to right. Given a vertex v = v(i, j) of the grid, we denote by row(v) and col(v) the row and
the column of the grid, respectively, that contain v. We say that Gh,` is a square grid iff h = `. The
boundary of the grid is R1 ∪ Rh ∪ W1 ∪ W` . We sometimes refer to R1 and Rh as the top and the
bottom boundary edges of the grid respectively, and to W1 and W` as the left and the right boundary
edges of the grid.
Given a subset R0 of consecutive rows of G and a subset W 0 of consecutive columns of G, the sub-grid
of G spanned by the rows in R0 and the columns in W 0 is the sub-graph of G induced by the set
{v | row(v) ∈ R0 , col(v) ∈ W 0 } of its vertices.
Given two vertices u = v(i, j) and u0 = v(i0 , j 0 ) of a grid G, the shortest-path distance between
them is denoted by d(u, u0 ). Given two vertex subsets X, Y ⊆ V (G), the distance between them
is d(X, Y ) = minu∈X,u0 ∈Y {d(u, u0 )}. When H, H 0 are subgraphs of G, we use d(H, H 0 ) to denote
d(V (H), V (H 0 )).
Wall Graphs. Let G = G`,h be a grid of length ` and height h. Assume that ` > 0 is an even
integer, and that h > 0. For every column Wj of the grid, let ej1 , . . . , ejh−1 be the edges of Wj indexed
in their top-to-bottom order. Let E ∗ (G) ⊆ E(G) contain all edges ejz , where z 6= j mod 2, and let Ĝ
be the graph obtained from G \ E ∗ (G), by deleting all degree-1 vertices from it. Graph Ĝ is called a
wall of length `/2 and height h (see Figure 1). Consider the subgraph of Ĝ induced by all horizontal
edges of the grid G that belong to Ĝ. This graph is a collection of h node-disjoint paths, that we refer
to as the rows of Ĝ, and denote them by R1 , . . . , Rh in this top-to-bottom order; notice that Rj is
also the jth row of the grid G for all j. Graph Ĝ contains a unique collection W of `/2 node-disjoint
paths that connect vertices of R1 to vertices of Rh and are internally disjoint from R1 and Rh . We
refer to the paths in W as the columns of Ĝ, and denote them by W1 , . . . , W`/2 in this left-to-right
order. Paths W1 , W`/2 , R1 and Rh are called the left, right, top and bottom boundary edges of Ĝ,
respectively, and their union is the boundary of Ĝ.
The 3COL(5) problem. The starting point of our reduction is the 3COL(5) problem. In this
problem, we are given a 5-regular graph G = (V, E). Note that, if n = |V | and m = |E|, then
m = 5n/2. We are also given a set C = {r, b, g} of 3 colors. A coloring χ : V → C is an assignment
of a color in C to every vertex in V . We say that an edge e = (u, v) is satisfied by the coloring χ iff
χ(u) 6= χ(v). The coloring χ is valid iff it satisfies every edge. We say that G is a Yes-Instance
iff there is a valid coloring χ : V → C. We say that it is a No-Instance with respect to some given
parameter , iff for every coloring χ : V → C, at most a (1 − )-fraction of the edges are satisfied by χ.
We use the following theorem of Feige et al. [FHKS03]:
Theorem 2.1 [Proposition 15 in [FHKS03]] There is some constant , such that distinguishing between the Yes-Instances and the No-Instances (with respect to ) of 3COL(5) is NP-hard.
5

A Two-Prover Protocol. We use the following two-prover protocol. The two provers are called
an edge-prover and a vertex-prover. Given a 5-regular graph G, the verifier selects an edge e = (u, v)
of G uniformly at random, and then selects a random endpoint (say v) of this edge. It then sends e to
the edge-prover and v to the vertex-prover. The edge-prover must return an assignment of colors from
C to u and v, such that the two colors are distinct; the vertex-prover must return an assignment of a
color from C to v. The verifier accepts iff both provers assign the same color to v. Given a 2-prover
game G, its value is the maximum acceptance probability of the verifier over all possible strategies of
the provers.
Notice that, if G is a Yes-Instance, then there is a strategy for both provers that guarantees acceptance with probability 1: the provers fix a valid coloring χ : V → C of G and respond to the queries
according to this coloring.
We claim that if G is a No-Instance, then for any strategy of the two provers, the verifier accepts
with probability at most (1 − /2). Note first that we can assume without loss of generality that
the strategies of the provers are deterministic. Indeed, if the provers have a probability distribution
over the answers to each query Q, then the edge-prover, given a query Q0 , can return an answer
that maximizes the acceptance probability of the verifier under the random strategy of the vertexprover. This defines a deterministic strategy for the edge-prover that does not decrease the acceptance
probability of the verifier. The vertex-prover in turn, given any query Q, can return an answer that
maximizes the acceptance probability of the verifier, under the new deterministic strategy of the edgeprover. The acceptance probability of this final deterministic strategy of the two provers is at least
as high as that of the original randomized strategy. The deterministic strategy of the vertex-prover
defines a coloring of the vertices of G. This coloring must dissatisfy at least m edges. The probability
that the verifier chooses one of these edge is at least . The response of the edge-prover on such an edge
must differ from the response of the vertex-prover on at least one endpoint of the edge. The verifier
chooses this endpoint with probability at least 12 , and so overall the verifier rejects with probability at
least /2. Therefore, if G is a Yes-Instance, then the value of the corresponding game is 1, and if it
is a No-Instance, then the value of the game is at most (1 − /2).
Parallel Repetition. We perform ` rounds of parallel repetition of the above protocol, for some
integer ` > 0, that may depend on n = |V (G)|. Specifically, the verifier chooses a sequence (e1 , . . . , e` )
of ` edges, where each edge ei is selected independently uniformly at random from E(G). For each
chosen edge ei , one of its endpoints vi is then chosen independently at random. The verifier sends
(e1 , . . . , e` ) to the edge-prover, and (v1 , . . . , v` ) to the vertex-prover. The edge-prover returns a coloring
of both endpoints of each edge ei . This coloring must satisfy the edge (so the two endpoints must
be assigned different colors), but it need not be consistent across different edges. In other words, if
two edges ei and ej share the same endpoint v, the edge-prover may assign different colors to each
occurrence of v. The vertex-prover returns a coloring of the vertices in (v1 , . . . , v` ). Again, if some
vertex vi repeats twice, the coloring of the two occurrences need not be consistent. The verifier
accepts iff for each 1 ≤ i ≤ `, the coloring of the vertex vi returned by both provers is consistent. (No
verification of consistency is performed across different i’s. So, for example, if vi is an endpoint of ej
for i 6= j, then it is possible that the two colorings do not agree and the verifier still accepts). We say
that a pair (A, A0 ) of answers to the two queries (e1 , . . . , e` ) and (v1 , . . . , v` ) is matching, or consistent,
iff it causes the verifier to accept. We let G ` denote this 2-prover protocol with ` repetitions.
Theorem 2.2 (Parallel Repetition) [Raz98, Hol07, Rao08] There is some constant 0 < γ 0 < 1,
such that for each 2-prover game G̃, if the value of G̃ is x, then the value of the game G̃ ` , obtained
0
from ` > 0 parallel repetitions of G̃, is xγ ` .

6

Corollary 2.3 There is some constant 0 < γ < 1, such that, if G is a Yes-Instance, then G ` has
value 1, and if G is a No-Instance, then G ` has value at most 2−γ` .
We now summarize the parameters and introduce some basic notation:
• Let QE denote the set of all possible queries to the edge-prover, so each query is an `-tuple of
edges. Then |QE | = m` = (5n/2)` . Each query has 6` possible answers – 6 colorings per edge.
The set of feasible answers is the same for each edge-query, and we denote it by AE .
• Let QV denote the set of all possible queries to the vertex-prover, so each query is an `-tuple of
vertices. Then |QV | = n` . Each query has 3` feasible answers – 3 colorings per vertex. The set
of feasible answers is the same for each vertex-query, and we denote it by AV .
• We think about the verifier as choosing a number of random bits, that determine the choices of
the queries Q ∈ QE and Q0 ∈ QV that it sends to the provers. We sometimes call each such
random choice a “random string”. The set of all such choices is denoted by R, where for each
R ∈ R, we denote R = (Q, Q0 ), with Q ∈ QE , Q0 ∈ QV — the two queries sent to the two
provers when the verifier chooses R. Then |R| = (2m)` = (5n)` , and each random string R ∈ R
is chosen with the same probability.
• It is important to note that each query Q = (e1 , . . . , e` ) ∈ QE of the edge-prover participates
in exactly 2` random strings (one random string for each choice of one endpoint per edge of
{e1 , . . . , e` }), while each query Q0 = (v1 , . . . , v` ) of the vertex-prover participates in exactly 5`
random strings (one random string for each choice of an edge incident to each of v1 , . . . , v` ).
A function f : QE ∪QV → AE ∪AV is called a global assignment of answers to queries iff for every query
Q ∈ QE to the edge-prover, f (Q) ∈ AE , and for every query Q0 ∈ QV to the vertex-prover, f (Q0 ) ∈ AV .
We say that f is a perfect global assignment iff for every random string R = (QE , QV ), (f (QE ), f (QV ))
is a matching pair of answers. The following simple theorem, whose proof appears in Section A of the
Appendix, shows that in the Yes-Instance, there are many perfect global assignments, that neatly
partition all answers to the edge-queries.
Theorem 2.4 Assume that G is a Yes-Instance. Then there are 6` perfect global assignments
f1 , . . . , f6` of answers to queries, such that:
• for each query Q ∈ QE to the edge-prover, for each possible answer A ∈ AE , there is exactly one
index 1 ≤ i ≤ 6` with fi (Q) = A; and
• for each query Q0 ∈ QV to the vertex-prover, for each possible answer A0 ∈ AV to Q0 , there are
exactly 2` indices 1 ≤ i ≤ 6` , for which fi (Q0 ) = A0 .
Two Graphs. Given a 3COL(5) instance G with |V (G)| = n, and an integer ` > 0, we associate a
graph H, that we call the constraint graph, with it. For every query Q ∈ QE ∪ QV , there is a vertex
v(Q) in H, while for each random string R = (Q, Q0 ), there is an edge e(R) = (v(Q), v(Q0 )). Notice
that H is a bipartite graph. We denote by U E the set of its vertices corresponding to the edge-queries,
and by U V the set of its vertices corresponding to the vertex-queries. Recall that |U E | = (5n/2)` ,
|U V | = n` ; the degree of every vertex in U E is 2` ; the degree of every vertex in U V is 5` , and
|E(H)| = |R| = (5n)` .
Assume now that we are given some subgraph H 0 ⊆ H of the constraint graph. We build a bipartite
graph L(H 0 ) associated with it (this graph takes into account the answers to the queries; it may be
7

convenient for now to think that H 0 = H, but later we will use smaller sub-graphs of H). The vertices
of L(H 0 ) are partitioned into two subsets:
• For each edge-query Q ∈ QE with v(Q) ∈ H 0 , for each possible answer A ∈ AE to Q, we
introduce a vertex v(Q, A). We denote by S(Q) the set of these 6` vertices corresponding to Q,
and we call them a group representing Q. We denote by Û E the resulting set of vertices:

Û E = v(Q, A) | (Q ∈ QE and v(Q) ∈ H 0 ), A ∈ AE .
• For each vertex-query Q0 ∈ QV with v(Q0 ) ∈ H 0 , for each possible answer A0 ∈ AV to Q0 , we
introduce 2` vertices v1 (Q0 , A0 ), . . . , v2` (Q0 , A0 ). We call all these vertices the copies of answer
A0 to query Q0 . We denote by S(Q0 ) the set of all vertices corresponding to Q0 :
n
o
S(Q0 ) = vi (Q0 , A0 ) | A0 ∈ AV , 1 ≤ i ≤ 2` ,
so |S(Q0 )| = 6` . We call S(Q0 ) the group representing Q0 . We denote by Û V the resulting set of
vertices:
o
n
Û V = vi (Q0 , A0 ) | (Q0 ∈ QV and v(Q0 ) ∈ H 0 ), A0 ∈ AV , 1 ≤ i ≤ 2` .
The final set of vertices of L(H 0 ) is Û E ∪ Û V . We define the set of edges of L(H 0 ) as follows. For
each random string R = (QE , QV ) whose corresponding edge e(R) belongs to H 0 , for every answer
A ∈ AE to QE , let A0 ∈ AV be the unique answer to QV consistent with A. For each copy vi (QV , A0 )
of answer A0 to query QV , we add an edge (v(QE , A), vi (QV , A0 )). Let
o
n
E(R) = (v(QE , A), vi (QV , A0 )) | A ∈ AE , A0 ∈ AV , A and A0 are consistent answers to R, 1 ≤ i ≤ 2`
be the set of the resulting edges, so |E(R)| = 6` · 2` = 12` . We denote by Ê the set of all edges of
L(H 0 ) — the union of the sets E(R) for all random strings R with e(R) ∈ H 0 .
Recall that we have defined a partition of the set Û E of vertices into groups S(Q) — one group for
each query Q ∈ QE with v(Q) ∈ H 0 . We denote this partition by U1 . Similarly, we have defined a
partition of Û V into groups, that we denote by U2 = S(Q0 ) | Q0 ∈ QV and v(Q0 ) ∈ H 0 . Recall that
for each group U ∈ U1 ∪ U2 , |U | = 6` .
Finally, we need to define bundles of edges in graph L(H 0 ). For every vertex v ∈ Û E ∪ Û V , we define
a partition B(v) of the set of all edges incident to v in L(H 0 ) into bundles, as follows. Fix some group
U ∈ U1 ∪ U2 that we have defined. If there is at least one edge of L(H 0 ) connecting v to the vertices
of U , then we define a bundle containing all edges connecting v to the vertices of U , and add this
bundle to B(v). Therefore, if v ∈ S(Q), then for each random string R in which Q participates, with
e(R) ∈ H 0 , we have defined one bundle of edges in B(v). For each vertex v ∈ Û E ∪ Û V , the set of all
edges incident to v is thus partitioned into a collection of bundles, that we denote by B(v), and we
denote β(v) = |B(v)|. Note that, if v ∈ S(Q) for someSquery Q ∈ QE ∪ QV , then β(v) is exactly the
degree of the vertex v(Q) in graph H 0 . Note also that v∈V (H 0 ) B(v) does not define a partition of the
S
S
edges of Ê, as each such edge belongs to two bundles. However, each of v∈Û E B(v) and v∈Û V B(v)
does define a partition of Ê. It is easy to verify that every bundle that we have defined contains
exactly 2` edges.
8

3

The (r, h)-Graph Partitioning Problem

We will use a graph partitioning problem as a proxy in order to reduce the 3COL(5) problem to NDPGrid. The specific graph partitioning problem is somewhat complex. We first define a simpler variant
of this problem, and then provide the intuition and the motivation for the more complex variant that
we eventually use.
In the basic (r, h)-Graph Partitioning problem, that we denote by (r,h)-GP, we are given a bipartite
graph G̃ = (V1 , V2 , E) and two integral parameters h, r > 0. A solution consists of a partition
(W1 , . . . , Wr ) of V1 ∪ V2 into r subsets, P
and for each 1 ≤ i ≤ r, a subset Ei ⊆ E(Wi ) of edges, such
that |Ei | ≤ h. The goal is to maximize i |Ei |.
One intuitive way to think about the (r,h)-GP problem is that we would like to partition the vertices of
G̃ into r clusters, that are roughly balanced (in terms of the number of edges in each cluster). However,
unlike the standard balanced partitioning problems, that attempt to minimize the number of edges
connecting the different clusters, our goal is to maximize the total number of edges that remain in the
clusters. We suspect that the (r,h)-GP problem is very hard to approximate; in particular it appears
to be somewhat similar to the Densest k-Subgraph problem (DkS). Like in the DkS problem, we are
looking for dense subgraphs of G̃ (the subgraphs G̃[Wi ]), but unlike DkS, where we only need to find
one such dense subgraph, we would like to partition all vertices of G̃ into a prescribed number of dense
subgraphs. We can prove that NDP-Grid is at least as hard as (r,h)-GP (to within polylogarithmic
factors; see below), but unfortunately we could not prove strong hardness of approximation results for
(r,h)-GP. In particular, known hardness proofs for DkS do not seem to generalize to this problem. To
overcome this difficulty, we define a slightly more general problem, and then use it as a proxy in our
reduction. Before defining the more general problem, we start with intuition.
Intuition: Given a 3COL(5) instance G, we can construct the graph H, and the graph L(H), as
described above. We can then view L(H) as an instance of (r,h)-GP, with r = 6` and h = |R|.
Assume that G is a Yes-Instance. Then we can use the perfect global assignments f1 , . . . , fr of
answers to the queries, given by Theorem 2.4, in order to partition the vertices of L(H) into r = 6`
clusters W1 , . . . , Wr , as follows. Fix some 1 ≤ i ≤ r. For each query Q ∈ QE to the edge-prover,
set Wi contains a single vertex v(Q, A) ∈ S(Q), where A = fi (Q). For each query Q0 ∈ QV to the
vertex-prover, set Wi contains a single vertex vj (Q0 , A0 ), where A0 = fi (Q0 ), and the indices j are
chosen so that every vertex vj (Q0 , A0 ) participates in exactly one cluster Wi . From the construction
of the graph L(H) and the properties of the assignments fi guaranteed by Theorem 2.4, we indeed
obtain a partition W1 , . . . , Wr of the vertices of L(H). For each 1 ≤ i ≤ r, we then set Ei = E(Wi ).
Notice that for every query Q ∈ QE ∪ QV , exactly one vertex of S(Q) participates in each cluster
Wi . Therefore, for each group U ∈ U1 ∪ U2 , each cluster Wi contains exactly one vertex from this
group. It is easy to verify that for each 1 ≤ i ≤ r, for each random string R ∈ R, set Ei contains
exactly one edge of E(R), and so |Ei | = |R| = h, and the solution value is h · r. Unfortunately, in the
No-Instance, we may still obtain a solution of a high value, as follows: instead of distributing, for
each query Q ∈ QE ∪ QV , the vertices of S(Q) to different clusters Wi , we may put all vertices of S(Q)
into a single cluster. While in our intended solution to the (r,h)-GP problem instance each cluster can
be interpreted as an assignment of answers to the queries, and the number of edges in each cluster
is bounded by the number of random strings satisfied by this assignment, we may no longer use this
interpretation with this new type of solutions2 . Moreover, unlike in the Yes-Instance solutions, if
we now consider some cluster Wi , and some random string R ∈ R, we may add several edges of E(R)
to Ei , which will further allow us to accumulate a high solution value. One way to get around this
2

We note that a similar problem arises if one attempts to design naive hardness of approximation proofs for DkS.

9

problem is to impose additional restrictions on the feasible solutions to the (r,h)-GP problem, which
are consistent with our Yes-Instance solution, and thereby obtain a more general (and hopefully
more difficult) problem. But while doing so we still need to ensure that we can prove that NDP-Grid
remains at least as hard as the newly defined problem. Recall the definition of bundles in graph L(H).
It is easy to verify that in our intended solution to the Yes-Instance, every bundle contributes at
most one edge to the solution. This motivates our definition of a slight generalization of the (r,h)-GP
problem, that we call (r, h)-Graph Partitioning with Bundles, or (r,h)-GPwB.
The input to (r,h)-GPwB problem is almost the same as before: we are given a bipartite graph G̃ =
(V1 , V2 , E), and two integral parameters h, r > 0. Additionally, we are given a partition U1 of V1 into
groups, and a partition U2 of V2 into groups, so that for each U ∈ U1 ∪ U2 , |U | = r. Using these
groups, we define bundles of edges as follows: for every vertex v ∈ V1 , for each group U ∈ U2 , such
that some edge of E connects v to a vertex of U , the set of all edges that connect v to the vertices
of U defines a single bundle. Similarly, for every vertex v ∈ V2 , for each group U ∈ U1 , all edges that
connect v to the vertices of U define a bundle. We denote, for each vertex v ∈ V1 ∪ V2 , by B(v) the set
of all bundles into which the edges incident to v are
S partitioned, and we denote by β(v) = |B(v)| the
number of such bundles. We also denote by B = v∈V1 ∪V2 B(v) – the set of all bundles. Note that as
before,
B is not a partition of E,
S
S but every edge of E belongs to exactly two bundles: one bundle in
v∈V1 B(v), and one bundle in
v∈V2 B(v). As before, we need to compute a partition (W1 , . . . , Wr ) of
V1 ∪ V2 into r subsets, and for each 1 ≤ i ≤ r, select a subset Ei ⊆ E(Wi ) of edges, such that |Ei | ≤ h.
But now there is an additional restriction: we require that for each 1 ≤ i P
≤ r, for every bundle B ∈ B,
Ei contains at most one edge e ∈ B. As before, the goal is to maximize i |Ei |.
Valid Instances and Perfect
Solutions. Given an instance I = (G̃ = (V1 , V2 , E), U1 , U2 , h, r) of
P
∗
(r,h)-GPwB, let β (I) =
v∈V1 β(v). Note that for any solution to I, the solution value must be
bounded by β ∗ (I), since for every vertex v ∈ V1 , for every bundle B ∈ B(v), at most one edge from
the bundle may contribute to the solution value. In all instances of (r,h)-GPwB that we consider, we
always set h = β ∗ (I)/r. Next, we define valid instances; they are defined so that the instances that
we obtain when reducing from 3COL(5) are always valid, as we show later.
Definition 1 We say that instance I of (r,h)-GPwB is valid iff h = β ∗ (I)/r and h ≥ maxv∈V1 ∪V2 {β(v)}.
Recall that for every group U ∈ U1 ∪ U2 , |U | = r. We now define perfect solutions to the (r,h)-GPwB
problem. We will ensure that our intended solutions in the Yes-Instance are always perfect, as we
show later.
Definition 2 We say that a solution ((W1 , . . . , Wr ), (E1 , . . . , Er )) to a valid (r,h)-GPwB instance I
is perfect iff:
• For each group U ∈ U1 ∪ U2 , exactly one vertex of U belongs to each cluster Wi ; and
• For each 1 ≤ i ≤ r, |Ei | = h.
Note that the value of a perfect solution to a valid instance I is h · r = β ∗ (I), and this is the largest
value that any solution can achieve.

3.1

From 3COL(5) to (r,h)-GPwB

Suppose we are given an instance G of the 3COL(5) problem, and an integral parameter ` > 0 (the
number of repetitions). Consider the corresponding constraint graph H, and suppose we are given
some subgraph H 0 ⊆ H. We define an instance I(H 0 ) of (r,h)-GPwB, as follows.
10

• The underlying graph is L(H 0 ) = (Û E , Û V , Ê);
• The parameters are r = 6` and h = |E(H 0 )|;
• The partition U1 of Û E is the same as before: the vertices of Û E are partitioned into groups
S(Q) — one group for each query Q ∈ QE with v(Q) ∈ V (H 0 ). Similarly, the partition U2 of
Û V into groups is also defined exactly as before, and contains, for each query Q0 ∈ QV with
v(Q0 ) ∈ V (H 0 ), a group S(Q0 ). (Recall that for all Q ∈ QE ∪ QV with v(Q) ∈ H 0 , |S(Q)| = 6` ).
Claim 3.1 Let G be an instance of the 3COL(5) problem, ` > 0 an integral parameter, and H 0 ⊆ H
a subgraph of the corresponding constraint graph. Consider the corresponding instance I(H 0 ) of (r,h)GPwB. Then I(H 0 ) is a valid instance, and moreover, if G is a Yes-Instance, then there is a perfect
solution to I(H 0 ).
Proof: We first verify that I(H 0 ) is a valid instance of (r,h)-GPwB. Recall that for a query Q ∈ QE
to the edge-prover and an answer A ∈ AE , the number of bundles incident to vertex v(Q, A) in L(H 0 )
is exactly the degree of the vertex v(Q) in graph H 0 . The total number of bundles
P incident to the
vertices of S(Q) is then the degree of v(Q) in H 0 times |AE |. Therefore, β ∗ (I) = v(Q,A)∈Û E |β(v)| =
|E(H 0 )| · |AE | = h · r. It is now immediate to verify that h = β ∗ (I)/r. Similarly, for a vertex
v = vj (Q0 , A0 ) ∈ U V , the number of bundles incident to v is exactly the degree of v in H 0 . Since
h = |E(H 0 )|, we get that h ≥ maxv∈V1 ∪V2 {β(v)}, and so I(H 0 ) is a valid instance.
Assume now that G is a Yes-Instance. We define a perfect solution ((W1 , . . . , Wr ), (E1 , . . . , Er ))
to this instance. Let {f1 , f2 , . . . , f6` } be the collection ofperfect global assignments of answers
to the queries, given by Theorem 2.4. Recall that U1 = S(Q) | Q ∈ QE , v(Q) ∈ H 0 and U2 =

S(Q0 ) | Q0 ∈ QV , v(Q0 ) ∈ H 0 , where each group in U1 ∪ U2 has cardinality r = 6` . We now fix some
1 ≤ i ≤ r, and define the set Wi of vertices. For each query Q ∈ QE to the edge-prover, if A = fi (Q),
then we add the vertex v(Q, A) to Wi . For each query Q0 ∈ QV to the vertex-prover, if A0 = fi (Q0 ),
then we select some index 1 ≤ j ≤ 2` , and add the vertex vj (Q0 , A0 ) to Wi . The indices j are chosen
so that every vertex vj (Q0 , A0 ) participates in at most one cluster Wi . From the construction of the
graph L(H 0 ) and the properties of the assignments fi guaranteed by Theorem 2.4, it is easy to verify
that W1 , . . . , Wr partition the vertices of L(H 0 ), and moreover, for each group S(Q) ∈ U1 ∪ U2 , each
set Wi contains exactly one vertex of S(Q).
Finally, for each 1 ≤ i ≤ r, we set Ei = E(Wi ). We claim that for each bundle B ∈ B, set Ei may
contain at most one edge of B. Indeed, let v ∈ Wi be some vertex, let U ∈ U1 ∪ U2 be some group,
and let B be the bundle containing all edges that connect v to the vertices of U . Since Wi contains
exactly one vertex of U , at most one edge of B may belong to Ei .
It now remains to show that |Ei | = h for all i. Fix some 1 ≤ i ≤ r. It is easy to verify that for each
random string R = (Q, Q0 ) with e(R) ∈ H 0 , set Wi contains a pair of vertices v(Q, A), vj (Q0 , A0 ), where
A and A0 are matching answers to Q and Q0 respectively, and so the corresponding edge connecting
this pair of vertices in L(H 0 ) belongs to Ei . Therefore, |Ei | = |E(H 0 )| = h.

3.2

From (r,h)-GPwB to NDP

The following definition will be useful for us later, when we extend our results to NDP and EDP on
wall graphs.
Definition 3 Let P be a set of paths in a grid Ĝ. We say that P is a spaced-out set iff for each pair
P, P 0 ∈ P of paths, d(V (P ), V (P 0 )) ≥ 2, and all paths in P are internally disjoint from the boundaries
of the grid Ĝ.
11

Note that if P is a set of paths that is spaced-out, then all paths in P are mutually node-disjoint. The
following theorem is central to our hardness of approximation proof.
Theorem 3.2 There is a constant c∗ > 0, and there is an efficient randomized algorithm, that, given a
valid instance I = (G̃, U1 , U2 , h, r) of (r,h)-GPwB with |E(G̃)| = M , constructs an instance Î = (Ĝ, M)
of NDP-Grid with |V (Ĝ)| = O(M 4 log2 M ), such that the following hold:
• If I has a perfect solution (of value β ∗ = β ∗ (I)), then with probability at least 12 over the
β∗
demand pairs, such
construction of Î, instance Î has a solution P that routes at least c∗ log
3
M
that the paths in P are spaced-out; and
• There is a deterministic efficient algorithm, that, given a solution P ∗ to the NDP-Grid
problem
|P ∗ |
instance Î, constructs a solution to the (r,h)-GPwB instance I, of value at least c∗ ·log3 M .
We note that the theorem is slightly stronger than what is needed in order to prove hardness of
approximation of NDP-Grid: if I has a perfect solution, then it is sufficient to ensure that the set
P of paths in the corresponding NDP-Grid instance Î is node-disjoint. But we will use the stronger
guarantee that it is spaced-out when extending our results to NDP and EDP in wall graphs. Note that
in the second assertion we are only guaranteed that the paths in P ∗ are node-disjoint. The proof of
the theorem is somewhat technical and is deferred to Section 5.
Assume now that we are given an instance G of 3COL(5), an integral parameter ` > 0, and a subgraph
H 0 ⊆ H of the corresponding constraint graph. Recall that we have constructed a corresponding
instance I(H 0 ) of (r,h)-GPwB. We can then use Theorem 3.2 to construct a (random) instance of
NDP-Grid, that we denote by Î(H 0 ). Note that |E(L(H 0 ))| ≤ 2O(`) · |E(H)| ≤ nO(`) . Let ĉ be a
constant, such that |E(L(H 0 ))| ≤ nĉ` for all H 0 ⊆ H; we can assume w.l.o.g. that ĉ > 1. We can also
assume w.l.o.g. that c∗ ≥ 1, where c∗ is the constant from Theorem 3.2, and we denote cYI = (ĉ · c∗ )3 .
We obtain the following immediate corollary of Theorem 3.2:
Corollary 3.3 Suppose we are given 3COL(5) instance G that is a Yes-Instance, an integer ` > 0,
and a subgraph H 0 ⊆ H of the corresponding constraint graph. Then with probability at least 21 , instance
Î(H 0 ) of NDP-Grid has a solution of value at least

|E(H 0 )|·6`
,
cYI `3 log3 n

where n = |V (G)|. (The probability is

over the random construction of Î(H 0 )).
Proof: From Claim 3.1, instance I(H 0 ) = (L(H 0 ), U1 , U2 , r, h) of (r,h)-GPwB is a valid instance, and it
has a perfect solution, whose value must be β ∗ = β ∗ (I(H 0 )) = h · r = |E(H 0 )| · 6` . From Theorem 3.2,
0 )|·6`
with probability at least 1/2, instance Î(H 0 ) of NDP-Grid has a solution of value at least |E(H
,
c∗ log3 M
0
where M = |E(L(H ))|. Since log M ≤ ĉ` log n, and the corollary follows.

4

The Hardness Proof

Let G be an input instance of 3COL(5). Recall that γ is the absolute constant from the Parallel
Repetition Theorem (Corollary 2.3). We will set the value of the parameter ` later, ensuring that
` > log2 n, where n = |V (G)|. Let α∗ = 2Θ(`/ log n) be the hardness of approximation factor that we
are trying to achieve.
Given the tools developed in the previous sections, a standard way to prove hardness of NDP-Grid
would work as follows. Given an instance G of 3COL(5) and the chosen parameter `, construct the
12

corresponding graph H (the constraint graph), together with the graph L(H). We then construct an
instance I(H) of (r,h)-GPwB as described in the previous section, and convert it into an instance Î(H)
of NDP-Grid.
We note that, if G is a Yes-Instance, then from Corollary 3.3, with constant probability there is a
`
solution to Î(H) of value c |R|·6
. Assume now that G is a No-Instance. If we could show that any
`3 log3 n
YI

solution to the corresponding (r,h)-GPwB instance I(H) has value less than

|R|·6`
,
c2YI ·α∗ `6 log6 n

we would

be done. Indeed, in such a case, from Theorem 3.2, every solution to the NDP-Grid instance Î(H)
`
∗
routes fewer than c α|R|·6
∗ `3 log3 n demand pairs. If we assume for contradiction that an α -approximation
YI
algorithm exists for NDP-Grid, then, if G is a Yes-Instance, the algorithm would have to return
`
a solution to Î(H) routing at least c α|R|·6
∗ `3 log3 n demand pairs, while, if G is a No-Instance, no
YI
such solution would exist. Therefore, we could use the α∗ -approximation algorithm for NDP-Grid to
distinguish between the Yes-Instances and the No-Instances of 3COL(5).
Unfortunately, we are unable to prove this directly. Our intended solution to the (r,h)-GPwB instance
I(H), defined over the graph L(H), for each query Q ∈ QE ∪ QV , places every vertex of S(Q) into a
distinct cluster. Any such solution will indeed have a low value in the No-Instance. But a cheating
solution may place many vertices from the same set S(Q) into some cluster Wj . Such a solution may
end up having a high value, but it may not translate into a good strategy for the two provers, that
satisfies a large fraction of the random strings. In an extreme case, for each query Q, we may place all
vertices of S(Q) into a single cluster Wi . The main idea in our reduction is to overcome this difficulty by
noting that such a cheating solution can be used to compute a partition of the constraint graph H. The
graph is partitioned into as many as 6` pieces, each of which is significantly smaller than the original
graph H. At the same time, a large fraction of the edges of H will survive the partitioning procedure.
Intuitively, if we now restrict ourselves to only those random strings R ∈ R, whose corresponding edges
have survived the partitioning procedure, then the problem does not become significantly easier, and
we can recursively apply the same argument to the resulting subgraphs of H. We make a significant
progress in each such iteration, since the sizes of the resulting sub-graphs of H decrease very fast. The
main tool that allows us to execute this plan is the following theorem.
Theorem 4.1 Suppose we are given an instance G of the 3COL(5) problem with |V (G)| = n, and an
integral parameter ` > log2 n, together with some subgraph H 0 ⊆ H of the corresponding constraint
graph H, and a parameter P > 1. Consider the corresponding instance I(H 0 ) of (r,h)-GPwB, and
assume that we are given a solution to this instance of value at least |E(H 0 )| · 6` /α, where α =
c2YI · α∗ · `6 log6 n. Then there is a randomized algorithm whose running time is O nO(`) · log P , that
returns one of the following:
• Either a randomized strategy for the two provers that satisfies, in expectation, more than a
2−γ`/2 -fraction of the constraints R ∈ R with e(R) ∈ E(H 0 ); or
• A collection H of disjoint sub-graphs of H 0 , such that for each H 00 ∈ H, |E(H 00 )| ≤ |E(H 0 )|/2γ`/16 ,
0
0 )|
P
and with probability at least (1 − 1/P ), H 00 ∈H |E(H 00 )| ≥ c |E(H
, for some universal constant
`2 α2
c0 .
We postpone the proof of the theorem to the following subsection, after we complete the hardness proof
for NDP-Grid. We assume for contradiction that we are given a factor-α∗ approximation algorithm
A for NDP-Grid (recall that α∗ = 2Θ(`/ log n) ). We will use this algorithm to distinguish between the
Yes-Instances and the No-Instances of 3COL(5). Suppose we are given an instance G of 3COL(5).

13

For an integral parameter ` > log2 n, let H be the constraint graph corresponding to G and `. We
next show a randomized algorithm, that uses A as a subroutine, in order to determine whether G is
a Yes-Instance or a No-Instance. The running time of the algorithm is nO(`) .
Throughout the algorithm, we maintain a collection H of sub-graphs of H, that we sometimes call clusters. Set H is in turn partitioned into two subsets: set H1 of active clusters, and set H2 of inactive clus0
ters. Consider now some inactive cluster
cluster defines a 2-prover game G(H 0 ), where
 E H ∈E H2 . This
E
the queries to the two provers are Q ∈ Q | v(Q ) ∈ V (H 0 ) , and QV ∈ QV | v(QV ) ∈ V (H 0 )
respectively, and the constraints of the verifier are R(H 0 ) = {R ∈ R | e(R) ∈ E(H 0 )}. For each inactive cluster H 0 ∈ H2 , we will store a (possibly randomized) strategy of the two provers for game
G(H 0 ), that satisfies at least a 2−γ`/2 -fraction of the constraints in R(H 0 ).
At the beginning, H contains a single cluster – the graph H, which is active. The algorithm is executed
while H1 6= ∅, and its execution is partitioned into phases. In every phase, we process each of the
clusters that belongs to H1 at the beginning of the phase. Each phase is then in turn is partitioned
into iterations, where in every iteration we process a distinct active cluster H 0 ∈ H1 . We describe an
iteration when an active cluster H 0 ∈ H1 is processed in Figure 2 (see also the flowchart in Figure 3).
If the algorithm terminates with H containing only inactive clusters, then we return “G is a YesInstance”.
Correctness. We establish the correctness of the algorithm in the following two lemmas.
Lemma 4.2 If G is a Yes-Instance, then with high probability, the algorithm returns “G is a YesInstance”.
Proof: Consider an iteration of the algorithm when an active cluster H 0 is processed. Notice that the
algorithm may only determine that G is a No-Instance in Step (3) or in Step (5b). We now analyze
these two steps.
Consider first Step (3). From Corollary 3.3, with probability at least 1/2, a random graph Î(H 0 ) has
0 )|·6`
a solution of value at least c|E(H
, and our α∗ -approximation algorithm to NDP-Grid must then
`3 log3 n
YI

return a solution of value at least

|E(H 0 )|·6`
cYI α∗ `3 log3 n

. Since we use n4` independent random constructions

of Î(H 0 ), with high probability, for at least one of them, we will obtain a solution of value at least
|E(H 0 )|6`
. Therefore, with high probability our algorithm will not return “G is a No-Instance”
cYI α∗ `3 log3 n
due to Step (3) in this iteration.
Consider now Step (5b). The algorithm can classify G as a No-Instance in this step only if
P
c0 |E(H 0 )|
00
. From Theorem 4.1, this happens with probability at most 1/P , and
H 00 ∈H |E(H )| <
`2 α2
from our setting of the parameter P to be nc` for a large enough constant c, with high probability our
algorithm will not return “G is a No-Instance” due to Step (5b) in this iteration.
It is not hard to see that our algorithm performs nO(`) iterations, and so, using the union bound, with
high probability, it will classify G as a Yes-Instance.
Lemma 4.3 If G is a No-Instance, then the algorithm always returns “G is a No-Instance”.
Proof: From Corollary 2.3, it is enough to show that, whenever the algorithm classifies G as a YesInstance, there is a strategy for the two provers, that satisfies more than a fraction-2−γ` of the
constraints in R.

14

Iteration for Processing a Cluster H 0 ∈ H1
1. Construct an instance I(H 0 ) of (r,h)-GPwB.
2. Use Theorem 3.2 to independently construct n4` instances Î(H 0 ) of the NDP-Grid
problem.
3. Run the α∗ -approximation algorithm A on each such instance Î(H 0 ). If the re0 )|6`
sulting solution, for each of these instances, routes fewer than c |E(H
∗ `3 log3 n demand
α
YI
pairs, halt and return “G is a No-Instance”.
4. Otherwise, fix any instance Î(H 0 ) for which the algorithm returned a solution
0 )|6`
routing at least c |E(H
demand pairs. Denote |E(L(H 0 ))| = M , and recall
α∗ `3 log3 n
YI

that M ≤ nĉ` . Use Theorem 3.2 to compute a solution ((W1 , . . . , Wr ), (E1 , . . . , Er ))
to the instance I(H 0 ) of the (r,h)-GPwB problem, of value at least:

|E(H 0 )| · 6`
|E(H 0 )| · 6`
|E(H 0 )| · 6`
|E(H 0 )| · 6`
≥
≥
=
.
α
(cYI α∗ `3 log3 n)(c∗ log3 M )
cYI c∗ ĉ3 α∗ `6 log6 n
c2YI α∗ `6 log6 n
5. Apply the algorithm from Theorem 4.1 to this solution, with the parameter P =
nc` , for a sufficiently large constant c.
(a) If the outcome is a strategy for the provers satisfying more than a 2−γ`/2 fraction of constraints R ∈ R with e(R) ∈ E(H 0 ), then declare cluster H 0
inactive and move it from H1 to H2 . Store the resulting strategy of the
provers.
(b) Otherwise, let H̃ be the collection of sub-graphs of H 0 returned by the algo0
0 )|
P
rithm. If H 00 ∈H |E(H 00 )| < c |E(H
, then return “G is a No-Instance”.
` 2 α2
0
Otherwise, remove H from H1 and add all graphs of H̃ to H1 .

Figure 2: An iteration description
Note that the original graph H has at most nĉ` edges. In every phase, the number of edges in each
active graph decreases by a factor of at least 2γ`/16 . Therefore, the number of phases is bounded by
O(log n). If the algorithm classifies G as a Yes-Instance,
S then it must terminate when no active
clusters remain. In every phase, the number of edges in H 0 ∈H E(H 0 ) goes down by at most a factor
`2 α2 /c0 . Therefore, at the end of the algorithm:
X
H 0 ∈H2

|E(H 0 )| ≥

|R|
(`2 α2 /c0 )O(log n)

=

(`14

·

(α∗ )2

|R|
|R|
= ∗ O(log n) .
12
O(log
n)
(α )
· log n)

By appropriately setting α∗ = 2Θ(`/ log n) , we will ensure that the number of edges remaining in the
inactive clusters H 0 ∈ H2 is at least |R|/2γ`/4 . Each such edge corresponds to a distinct random
string R ∈ R. Recall that for each inactive cluster H 0 , there is a strategy for the provers in the
corresponding game G(H 0 ) that satisfies at least |E(H 0 )|/2γ`/2 of its constraints. Taking the union of
15

Figure 3: Flowchart for an iteration execution
all these strategies, we can satisfy more than |R|/2γ` constraints of R, contradicting the fact that G
is a No-Instance.
Running Time and the Hardness Factor. As observed above, our algorithm has at most nO(`)
iterations, where in every iteration it processes a distinct active cluster H 0 ⊆ H. The corresponding
graph L(H 0 ) has at most nO(`) edges, and so each of the nO(`) resulting instances of NDP-Grid contains
at most nO(`) vertices. Therefore, the overall running time of the algorithm is nO(`) . From the above
analysis, if G is a No-Instance, then the algorithm always classifies it as such, and if G is a YesInstance, then the algorithm classifies it as a Yes-Instance with high probability. The hardness
factor that we obtain is α∗ = 2Θ(`/ log n) , while we only apply our approximation algorithm to instances
of NDP-Grid containing at most N = nO(`) vertices. The running time of the algorithm is nO(`) , and
it is a randomized algorithm with a one-sided error.
1−2/(p+1)

(1−)

) , giving us a 2(log n)
Setting ` = logp n for a large enough integer p, we obtain α∗ = 2Θ((log N )
hardness of approximation for NDP-Grid for any constant , assuming NP 6⊆ RTIME(npoly log n ).
δ

-

δ

Setting ` = nδ for some constant δ, we get that N = 2O(n log n) and α∗ = 2Θ(n / log n) , giving us a
2
δ
nΩ(1/(log log n) ) -hardness of approximation for NDP-Grid, assuming that NP 6⊆ RTIME(2n ) for some
constant δ > 0.

4.1

Proof of Theorem 4.1

Recall that each edge of graph H 0 corresponds to some constraint R ∈ R. Let R0 ⊆ R be the set
of all constraints R with e(R) ∈ E(H 0 ). Denote
the solution to the (r,h)-GPwB instance I(H 0 ) by
S
r
((W1 , . . . , Wr ), (E1 , . . . , Er )), and let E 0 = i=1 Ei . Recall that for each random string R ∈ R0 , there
is a set E(R) of 12` edges in graph L(H 0 ) representing R. Due to the way these edges are partitioned
into bundles, at most 6` edges of E(R) may belong to E 0 . We say that a random string R ∈ R0 is good
iff E 0 contains at least 6` /(2α) edges of E(R), and we say that it is bad otherwise.
Observation 4.4 At least |R0 |/(2α) random strings of R0 are good.
Proof: Let x denote the fraction of good random strings in R0 . A good random string contributes at
most 6` edges to E 0 , while a bad random string contributes at most 6` /(2α). If x < 1/(2α), then a
simple accounting shows that |E 0 | < |R0 | · 6` /α = |E(H 0 )| · 6` /α, a contradiction.
16

Consider some random string R ∈ R0 , and assume that R = (QE , QV ). We denote by E 0 (R) =
E(R) ∩ E 0 . Intuitively, say that a cluster Wi is a terrible cluster for R if the number of edges of E(R)
that lie in Ei is much smaller than |QE ∩ Wi | or |QV ∩ Wi |. We now give a formal definition of a
terrible cluster.
Definition 4 Given a random string R ∈ R and an index 1 ≤ i ≤ 6` , we say that a cluster Wi is a
terrible cluster for R, if:
• either |E 0 (R) ∩ Ei | < |Wi ∩ S(QV )|/(8α); or
• |E 0 (R) ∩ Ei | < |Wi ∩ S(QE )|/(8α).
We say that an edge e ∈ E 0 (R) is a terrible edge if it belongs to the set Ei , where Wi is a terrible
cluster for R.
Observation 4.5 For each good random string R ∈ R0 , at most 6` /(4α) edges of E 0 (R) are terrible.
Proof: Assume for contradiction that more than 6` /(4α) edges of E 0 (R) are terrible. Denote R =
(QE , QV ). Consider some such terrible edge e ∈ E 0 (R), and assume that e ∈ Ei for some cluster Wi ,
that is terrible for R. We say that e is a type-1 terrible edge iff |E 0 (R) ∩ Ei | < |Wi ∩ S(QV )|/(8α),
and it is a type-2 terrible edge otherwise, in which case |E 0 (R) ∩ Ei | < |Wi ∩ S(QE )|/(8α) must hold.
Let E 1 (R) and E 2 (R) be the sets of all terrible edges of E 0 (R) of types 1 and 2, respectively. Then
either |E 1 (R)| > 6` /(8α), or |E 2 (R)| > 6` /(8α) must hold.
Assume first that |E 1 (R)| > 6` /(8α). Fix some index 1 ≤ i ≤ 6` , such that Wi is a cluster that is
terrible for R, and |E(R) ∩ Ei | < |Wi ∩ S(QV )|/(8α). We assign, to each edge e ∈ Ei ∩ E 1 (R), a
set of 8α vertices of Wi ∩ S(QV ) arbitrarily, so that every vertex is assigned to at most one edge;
we say that the corresponding edge is responsible for the vertex. Every edge of Ei ∩ E 1 (R) is now
responsible for 8α distinct vertices of Wi ∩ S(QV ). Once we finish processing all such clusters Wi , we
will have assigned, to each edge of E 1 (R), a set of 8α distinct vertices of S(QV ). We conclude that
|S(QV )| ≥ 8α|E 1 (R)| > 6` . But |S(QV )| = 6` , a contradiction.
The proof for the second case, where |E 2 (R)| > 6` /(16α) is identical, and relies on the fact that
|S(QE )| = 6` .
We will use the following simple observation.
Observation 4.6 Let R ∈ R0 be a good random string, with R = (QE , QV ), and let 1 ≤ i ≤ 6`
be an index, such that Wi is not terrible for R. Then |Wi ∩ S(QV )| ≥ |Wi ∩ S(QE )|/(8α) and
|Wi ∩ S(QE )| ≥ |Wi ∩ S(QV )|/(8α).
Proof: Assume first for contradiction that |Wi ∩ S(QV )| < |Wi ∩ S(QE )|/(8α). Consider the edges
of E(R) ∩ Ei . Each such edge must be incident to a distinct vertex of S(QV ). Indeed, if two edges
(e, e0 ) ∈ E(R) ∩ Ei are incident to the same vertex vj (QV , A) ∈ S(QV ), then, since the other endpoint
of each such edge lies in S(QE ), the two edges belong to the same bundle, a contradiction. Therefore,
|Ei ∩ E(R)| ≤ |Wi ∩ S(QV )| < |Wi ∩ S(QE )|/(8α), contradicting the fact that Wi is not a terrible
cluster for R.
The proof for the second case, where |Wi ∩ S(QE )| < |Wi ∩ S(QV )|/(8α) is identical. As before, each
edge of E(R) ∩ Ei must be incident to a distinct vertex of S(QE ), as otherwise, a pair e, e0 ∈ E(R)
of edges that are incident on the same vertex v(QE , A) ∈ S(QE ) belong the same bundle. Therefore,
17

|Ei ∩ E(R)| ≤ |Wi ∩ S(QE )| < |Wi ∩ S(QV )|/(8α), contradicting the fact that Wi is not a terrible
cluster for R.
For each good random string R ∈ R0 , we discard the terrible edges from set E 0 (R), so |E 0 (R)| ≥ 6` /(4α)
still holds.
Let z = 2γ`/8 . We say that cluster Wi is heavy for a random string R = (QE , QV ) ∈ R0 iff |Wi ∩
S(QE )|, |Wi ∩ S(QV )| > z. We say that an edge e ∈ E 0 (R) is heavy iff it belongs to set Ei , where
Wi is a heavy cluster for R. Finally, we say that a random string R ∈ R0 is heavy iff at least half of
the edges in E 0 (R) are heavy. Random strings and edges that are not heavy are called light. We now
consider two cases. The first case happens if at least half of the good random strings are light. In this
case, we compute a randomized strategy for the provers to choose assignment to the queries, so that
at least a 2−γ`/2 -fraction of the constraints in R0 are satisfied in expectation. In the second case, at
least half of the good random strings are heavy. We then compute a partition H of H 0 as desired. We
now analyze the two cases. Note that if |E(H 0 )| < z/(8α), then Case 2 cannot happen. This is since
h = |E(H 0 )| < z/(8α) in this case, and so no random strings may be heavy. Therefore, if H 0 is small
enough, we will return a strategy of the provers that satisfies a large fraction of the constraints in R0 .
Case 1. This case happens if at least half of the good random strings are light. Let L ⊆ R0 be the
set of the good light random strings, so |L| ≥ |R0 |/(4α). For each such random string R ∈ L, we
let E L (R) ⊆ E 0 (R) be the set of all light edges corresponding to R, so |E L (R)| ≥ 6` /(8α). We now
define a randomized algorithm to choose an answer to every query Q ∈ QE ∪ QV with v(Q) ∈ H 0 .
Our algorithm chooses a random index 1 ≤ i ≤ r. For every query Q ∈ QE ∪ QV with v(Q) ∈ H 0 ,
we consider the set A(Q) of all answers A, such that some vertex v(Q, A) belongs to Wi (for the case
where Q ∈ QV , the vertex is of the form vj (Q, A)). We then choose one of the answers from A(Q)
uniformly at random, and assign it to Q. If A(Q) = ∅, then we choose an arbitrary answer to Q.
We claim that the expected number of satisfied constraints of R0 is at least |R0 |/2γ`/2 . Since L ≥
|R0 |/(4α), it is enough to show that the expected fraction the good light constraints that are satisfied
is at least 4α|L|/2γ`/2 , and for that it is sufficient to show that each light constraint R ∈ L is satisfied
with probability at least 4α/2γ`/2 .
Fix one such constraint R = (QE , QV ) ∈ L, and consider an edge e ∈ E L (R). Assume that e connects
a vertex v(QE , A) to a vertex vj (QV , A0 ), and that e ∈ Ei . We say that edge e is happy iff our
algorithm chose the index i, the answer A to query QE , and the answer A0 to query QV . Notice that
due to our construction of bundles, at most one edge e ∈ E L (R) may be happy with any choice of
the algorithm; moreover, if any edge e ∈ E L (R) is happy, then the constraint R is satisfied. The
probability that a fixed edge e is happy is at least 1/(8 · 6` z 2 α). Indeed, we choose the correct index
i with probability 1/6` . Since e belongs to Ei , Wi is a light cluster for R, and so either |S(QE )| ≤ z,
or |S(QV )| ≤ z. Assume without loss of generality that it is the former; the other case is symmetric.
Then, since e is not terrible, from Observation 4.6, |S(QV )| ≤ 8αz, and so |A(QV )| ≤ 8αz, while
|A(QE )| ≤ z. Therefore, the probability that we choose answer A to QE and answer A0 to AV is
at least 1/(8αz 2 ), and overall, the probability that a fixed constraint R ∈ L is satisfied is at least
|E L (R)|/(8 · 6` z 2 α) ≥ 1/(64z 2 α2 ) ≥ 4α/2γ`/2 , since z = 2γ`/8 , and α < 2γ`/32 .
Case 2. This case happens if at least half of the good random strings are heavy. Let R00 ⊆ R0 be
the set of the heavy random strings, so |R00 | ≥ |R0 |/(4α). For each such random string R ∈ R00 , we
let E H (R) ⊆ E 0 (R) be the set of all heavy edges corresponding to R. Recall that |E H (R)| ≥ 6` /(8α).
Fix some heavy random string R ∈ R00 and assume that R = (QE , QV ). For each 1 ≤ i ≤ r, let
Ei (R) = E H (R) ∩ Ei . Recall that, if Ei (R) 6= ∅, then |Wi ∩ S(QE )|, |Wi ∩ S(QV )| ≥ z must hold,
18

and, from the definition of terrible clusters, |Ei (R)| ≥ z/(8α). It is also immediate that |Ei (R)| ≤
|E 0 (R)| ≤ 6` .

We partition the set 1, . . . , 6` of indices into at most log(|E H (R)|) ≤ log(6` ) classes, where index
1 ≤ y ≤ 6` belongs to class Cj (R) iff 2j−1 < |E H (R) ∩ Ey | ≤ 2j . Then there is some index jR , so that
P
H
H
`
y∈Cj (R) |E (R) ∩ Ey | ≥ |E (R)|/ log(6 ). We say that R chooses the index jR . Notice that:
R

X

|E H (R) ∩ Ey | ≥

y∈CjR (R)

|E H (R)|
6`
≥
.
8`α log 6
log(6` )

Moreover,
|CjR (R)| ≥

6`
|E H (R)|
.
≥
8 · 2j · `α log 6
log(6` ) · 2j

(1)

Let j ∗ be the index that was chosen by at least |R00 |/ log(6` ) random strings, and let R∗ ⊆ R00 be the
set of all random strings that chose j ∗ . We are now ready to define a collection H = {H1 , . . . , H6` } of
sub-graphs of H 0 . We first define the sets of vertices in these subgraphs, and then the sets of edges.
Choose a random ordering of the clusters W1 , . . . , W6` ; re-index the clusters according to this ordering.
For each query Q ∈ QE ∪QV with v(Q) ∈ H 0 , add the vertex v(Q) to set V (Hi ), where i is the smallest
∗
index for which Wi contains at least 2j −1 vertices of S(Q); if no such index i exists, then we do not
add v(Q) to any set.
In order to define the edges of each graph Hi , for every random string R = (QE , QV ) ∈ R∗ , if
i ∈ Cj ∗ (R), and both v(QE ) and v(QV ) belong to V (Hi ), then we add the corresponding edge e(R) to
E(Hi ). This completes the definition of the family H = {H1 , . . . , H6` } of subgraphs of H 0 . We now
show that the family H of graphs has the desired properties. It is immediate to verify that the graphs
in H are disjoint.
Claim 4.7 For each 1 ≤ i ≤ 6` , |E(Hi )| ≤ |E(H 0 )|/2γ`/16 .
Proof: Fix some index 1 ≤ i ≤ 6` . An edge e(R) may belong to Hi only if R ∈ R∗ , and i ∈ Cj ∗ (R).
In that case, Ei contained at least z/(8α) edges of E(R) (since Wi must be heavy for R and it is
not terrible for R). Therefore, the number of edges in Hi is bounded by |Ei | · 8α/z ≤ 8αh/z =
8α|E(H 0 )|/2γ`/8 ≤ |E(H 0 )|/2γ`/16 , since α ≤ 2γ`/32 .
0 )|
P
Claim 4.8 E [ ri=1 |E(Hi )|] ≥ 128`|E(H
2 α2 log2 6 .
00
`
0
`
∗
Proof: Recall that |R∗ | ≥
Sr|R |/ log(6 ) ≥ |R |/(4α log(6 )). EWe Vnow fix R ∈ R and analyze the
probability that e(R) ∈ i=1 E(Hi ). Assume that R = (Q , Q ). Let J be the set of indices
∗
∗
1 ≤ y ≤ 6` , such that |Wi ∩ S(QV )| ≥ 2j −1 . Clearly, |J| ≤ 6` /2j −1 , and v(QV ) may only belong to
∗
graph Hi if i ∈ J. Similarly, let J 0 be the set of indices 1 ≤ y ≤ 6` , such that |Wi ∩ S(QE )| ≥ 2j −1 .
∗
As before, |J 0 | ≤ 6` /2j −1 , and v(QE ) may only belong to graph Hi if i ∈ J. Observe that every index
6`
y ∈ Cj ∗ (R) must belong to J ∩ J 0 , and, since j ∗ = jR , from Equation (1), |Cj ∗ (R)| ≥ 8·2j ∗ ·`α
.
log 6

Let y ∈ J ∪ J 0 be the first index that occurs in our random ordering. If y ∈ Cj ∗ (R), then edge e(R) is
added to Hy . The probability of this happening is at least:
∗

|Cj ∗ (R)|
6` /(8 · 2j · `α log 6)
1
≥
=
.
∗ −1
0
`
j
|J ∪ J |
32`α log 6
2 · 6 /2
19

Overall, the expectation of

Pr

i=1 |E(Hi )|

is at least:

|R∗ |
|R0 |
|E(H 0 )|
≥
=
.
32`α log 6
128`2 α2 log2 6
128`2 α2 log2 6
P
Denote the expectation ofP ri=1 |E(Hi )| by µ, and let c = 128 log2 6, so that µ = |E(H 0 )|/(c`2 α2 ).
Let E be the event that ri=1 |E(Hi )| ≥ |E(H 0 )|/(2c`2 α2 ) = µ/2. We claim that E happens with
2 ). Indeed, assume that it happens with probability p < 1/(2c`2 α2 ).
probability at least 1/(2c`2 αP
P
If E does not happen, then Pri=1 |E(Hi )| ≤ µ/2, and if it happens, then ri=1 |E(Hi )| ≤ |E(H 0 )|.
Overall, this gives us that E [ ri=1 |E(Hi )|] ≤ (1 − p)µ/2 + p|E(H 0 )| < µ, a contradiction. We repeat
the algorithm for constructing H O(`2 α2 poly log n log P ) times. We are then guaranteed that with
probability at least (1 − 1/P ), event E happens in at least one run of the algorithm. It is easy to verify
that the running time of the algorithm is bounded by O(nO(`) · log P ), since |V (L(H 0 ))| ≤ nO(`) .

5

From (r,h)-GPwB to NDP-Grid

In this section we prove Theorem 3.2, by providing a reduction from (r,h)-GPwB to NDP-Grid. We
assume that we are given an instance I = (G̃ = (V1 ∪ V2 , E), U1 , U2 , h, r) of (r,h)-GPwB. Let |V1 | =
N1 , |V2 | = N2 , P
|E| = M , and N = N1 + N2 . We assume that I is a valid instance, so, if we denote by
∗
∗
β = β (I) = v∈V1 β(v), then h = β ∗ /r, and h ≥ maxv∈V1 ∪V2 {β(v)}.
We start by describing a randomized construction of the instance Î = (Ĝ, M) of NDP-Grid.

5.1

The Construction

Fix an arbitrary ordering ρ of the groups in U1 . Using ρ, we define an ordering σ of the vertices of V1 ,
as follows. The vertices that belong to the same group U ∈ U1 are placed consecutively in the ordering
σ, in an arbitrary order. The ordering between the groups in U1 is the same as their ordering in ρ. We
assume that V1 = {v1 , v2 , . . . , vN1 }, where the vertices are indexed according to their order in σ. Next,
0
we select a random ordering ρ0 of the groups in U2 . We then define an ordering
 0 0 σ of0 the vertices of
0
V2 exactly as before, using the ordering ρ of U2 . We assume that V2 = v1 , v2 , . . . , vN2 , where the
vertices are indexed according to their ordering in σ 0 . We note that the choice of the ordering ρ0 is
the only randomized part of our construction.
Consider some vertex v ∈ V1 . Recall that B(v) denotes the partition of the edges incident to v into
bundles, where every bundle is a non-empty subsets of edges, and that β(v) = |B(v)|. Each such
bundle B ∈ B(v) corresponds to a single group U (B) ∈ U2 , and contains all edges that connect v to
the vertices of U (B). The ordering ρ0 of the groups in U2 naturally induces an ordering of the bundles
in B(v),where B appears before B 0 in the ordering iff U (B) appears before U (B 0 ) in ρ0 . We denote
B(v) = B1 (v), B2 (v), . . . , Bβ(v) (v) , where the bundles are indexed according to this ordering.
Similarly, for a vertex v 0 ∈ V2 , every bundle B ∈ B(v 0 ) corresponds to a group U (B) ∈ U1 , and contains
all edges that connect v 0 to the vertices of U (B). As before, the ordering
ρ of the groups in U1 naturally

defines an ordering of the bundles in B(v 0 ). We denote B(v 0 ) = B1 (v 0 ), B2 (v 0 ), . . . , Bβ(v0 ) (v 0 ) , and
we assume that the bundles are indexed according to this ordering.
We are now ready to define the instance Î = (Ĝ, M)
from the input instance (G̃ =
 of NDP-Grid,

(V1 , V2 , E), U1 , U2 , h, r) of (r,h)-GPwB. Let ` = 2048 · M 2 · log M . The graph Ĝ is simply the (` × `)grid, so V (Ĝ) = O(M 4 log2 M ) as required. We now turn to define the set M of the demand pairs.
20

We first define the set M itself, without specifying the locations of the corresponding vertices in Ĝ,
and later specify a mapping of all vertices participating in the demand pairs to V (Ĝ).
Consider the underlying graph G̃ = (V1 , V2 , E) of the (r,h)-GPwB problem instance. Initially, for
every edge e = (u, v) ∈ E, with u ∈ V1 , v ∈ V2 , we define a demand pair (s(e), t(e)) representing e,
and add it to M, so that the vertices participating in the demand pairs are all distinct. Next, we
process the vertices v ∈ V1 ∪ V2 one-by-one. Consider first some vertex v ∈ V1 , and some bundle
B ∈ B(v). Assume that B = {e1 , . . . , ez }. Recall that for each 1 ≤ i ≤ z, set M currently contains a demand pair (s(ei ), t(ei )) representing ei . We unify all vertices s(e1 ), . . . , s(ez ) into a single
vertex sB . We then replace the demand pairs (s(e1 ), t(e1 )), . . . , (s(ez ), t(ez )) with the demand pairs
(sB , t(e1 )), . . . , (sB , t(ez )). Once we finish processing all vertices in V1 , we perform the same procedure
for every vertex of V2 : given a vertex v 0 ∈ V2 , for every bundle B 0 ∈ B(v 0 ), we unify all destination
vertices t(e) with e ∈ B 0 into a single destination vertex, that we denote by tB 0 , and we update M
accordingly. This completes the definition of the set M of the demand pairs.
Observe that each edge of e ∈ E still corresponds to a unique demand pair in M, that we will denote
by (sB(e) , tB 0 (e) ), where B(e) and B 0 (e) are the two corresponding bundles containing e. Given a subset

E 0 ⊆ E of edges of G̃, we denote by M(E 0 ) = (sB(e) , tB 0 (e) ) | e ∈ E 0 the set of all demand pairs
corresponding to the edges of E 0 .
In order to complete the reduction, we need to show a mapping of all source and all destination vertices
of M to the vertices of Ĝ. Let R0 and R00 be two rows of the grid Ĝ, lying at a distance at least `/4
from each other and from the top and the bottom boundaries of the grid. We will map all vertices of
S(M) to R0 , and all vertices of T (M) to R00 .
Locations of the sources. Let K1 , K2 , . . . , KN1 be a collection of N1 disjoint sub-paths of R0 ,
where each sub-path contains 1024 · dh · log M e vertices; the sub-paths are indexed according to their
left-to-right ordering on R0 , and every consecutive pair of the paths is separated by at least 10M
vertices from each other and from the left and the right boundaries of Ĝ. Observe that the width
` of the grid is large enough to allow this, as h ≤ M must hold. For all 1 ≤ i ≤ N1 , we call Ki
the block representing the vertex vi ∈ V1 . We now fix some 1 ≤ i ≤ N1 and consider the block Ki
representing the vertex vi . We map the source vertices sB1 (vi ) , sB2 (vi ) , . . . , sBβ(v ) (vi ) to vertices of Ki ,
i
so that they appear on Ki in this order, so that every consecutive pair of sources is separated by
exactly 512 · dh · log M/β(vi )e vertices.
0
Locations of the destinations. Similarly, we let K10 , K20 , . . . , KN
be a collection of N2 disjoint
2
00
sub-paths of R , each of which contains 1024 · dh · log M e vertices, so that the sub-paths are indexed
according to their left-to-right ordering on R00 , and every consecutive pair of the paths is separated
by at least 10M vertices from each other and from the left and the right boundaries of Ĝ. We call
Ki0 the block representing the vertex vi0 ∈ V2 . We now fix some 1 ≤ i ≤ N2 and consider the block Ki0
representing the vertex vi0 . We map the destination vertices tB1 (vi0 ) , tB2 (vi0 ) , . . . , tBβ(v0 ) (vi0 ) to vertices of
i

Ki0 , so that they appear on Ki0 in this order, and every consecutive pair of destinations is separated
by exactly 512 · dh · log M/β(vi0 )e vertices.
This concludes the definition of the instance Î = (Ĝ, M) of NDP-Grid. In the following subsections
we analyze its properties. The following immediate observation will be useful to us.
Observation 5.1 Consider a vertex vj ∈ V1 , and let Nj ⊆ M be any subset of demand pairs, whose
sources are all distinct and lie on Kj . Assume that Nj = {(s1 , t1 ), . . . , (sy , ty )}, where the demand
pairs are indexed according to the left-to-right ordering of their source vertices on Kj . Then t1 , . . . , ty
appear in this left-to-right order on R00 .
21

We will also use the following two auxiliary lemmas, whose proofs are straightforward and are deferred
to Section B of the Appendix.
Auxiliary Lemmas Assume that we are given a set U of n items, such that P of the items are
pink, and Y = n − P items are yellow. Consider a random permutation π of these items.
Lemma 5.2 For any log n ≤ µ ≤ Y , the probability that there is a sequence of d4nµ/P e consecutive
items in π that are all yellow, is at most n/eµ .
 
Lemma 5.3 For any log n ≤ µ ≤ P , the probability that there is a set S of nµ
consecutive items in
P
π, such that more than 4µ of the items are pink, is at most n/4µ .

5.2

From Partitioning to Routing

The goal of this subsection is to prove the following theorem.
Theorem 5.4 Suppose we are given a valid instance I = (G̃ = (V1 , V2 , E), U1 , U2 , h, r) of (r,h)-GPwB,
such that I has a perfect solution. Then with probability at least 1/2 over the random choices made
in the construction of the corresponding instance Î of NDP-Grid, there is a solution to Î, routing
Ω(β ∗ (I)/ log3 M ) demand pairs via a set of spaced-out paths.
The remainder of this subsection is devoted to the proof of the theorem. We assume w.l.o.g. that
|E| = M > 250 , as otherwise, since β ∗ (I) ≤ |E|, routing a single demand pair is sufficient.
Let ((W1 , . . . , Wr ), (E1 , . . . , Er )) be a perfect solution to I. Recall that by the definition of a perfect
solution, for each group U ∈ U1 ∪ U2 , every set Wi contains exactly one vertex of U , and moreover, for
each 1 ≤ i ≤ r, |Ei | = h = β ∗ (I)/r.
S
We let E 0 = ri=1 Ei , so |E 0 | = β ∗ (I) = hr. Let M0 ⊆ M be the set of all demand pairs corresponding
to the edges of E 0 . Note that we are guaranteed that no two demand pairs in M0 share a source or
a destination, since no two edges of E 0 belong to the same bundle.
Next we define a property of subsets of the demand pairs, called a distance property. We later show
that every subset M0 ⊆ M0 of demand pairs that has this property can be routed via spaced-out
paths, and that there is a large subset M0 ⊆ M0 of the demand pairs with this property.
Given a subset M0 ⊆ M0 of the demand pairs, we start by defining an ordering σM0 of the destination
vertices in T (M0 ). This ordering is somewhat different from the ordering of the vertices of T (M0 ) on
row R00 . We first provide a motivation and an intuition for this new ordering σM0 . Recall that the rows
R0 and R00 of Ĝ, where all source and all destination vertices lie, respectively, are located at a distance
at least `/4 from each other and from the grid boundaries. Let R be any row of Ĝ, lying between R0
and R00 , at a distance at least `/16 from both R0 and R00 . Let X be some subset of |M0 | vertices of
R. If we index the vertices of T (M0 ) as t1 , t2 , . . . , t|M0 | according to their order in the new ordering
σM0 , then we view the ith vertex of X, that we denote by xi , as representing the terminal ti . For
each 1 ≤ i ≤ |M0 |, we denote the source vertex corresponding to ti by si , that is, (si , ti ) ∈ M0 . Note
that the ordering of the vertices of S(M0 ) on R0 may be completely different from the one induced by
these indices. Similarly, the ordering of the vertices of T (M0 ) on R00 may be inconsistent with this
indexing. Eventually, we will construct a set P of spaced-out paths routing the demand pairs in M0 ,
so that the path Pi ∈ P, connecting si to ti , intersects the row R exactly once – at the vertex xi . In
this way, we will use the ordering σM0 of the destination vertices in T (M0 ) to determine the order in
which the path of P intersect R.
22

Assume now that we are given some subset M0 ⊆ M0 of demand pairs. Recall that the sources and
the destinations of all demand pairs in M0 are distinct. We are now ready to define the ordering σM0
of T (M0 ). We partition the vertices of T (M0 ) into subsets J1 , J2 , . . . , Jr , as follows. Consider some
vertex vj0 ∈ V2 of G̃, and assume that it lies in the cluster Wi . Then all destination vertices of T (M0 )
that belong to the corresponding block Kj0 are added to the set Ji . To obtain the final ordering σM0 ,
we place the vertices of J1 , J2 , . . . , Jr in this order, where within each set Ji , the vertices are ordered
according to their ordering along the row R00 . Notice that a selection of a subset M0 ⊆ M0 completely
determines the ordering σM0 . Given two demand pairs (s, t), (s0 , t0 ) ∈ M0 , we let NM0 (s, s0 ) denote
the number of destination vertices that lie between t and t0 in the ordering σM0 (note that this is
well-defined as the demand pairs in M0 do not share their sources or destinations). Recall that d(s, s0 )
is the distance between s and s0 in graph Ĝ.
Definition 5 Suppose we are given a subset M0 ⊆ M0 of the demand pairs. We say that two distinct
vertices s, s0 ∈ S(M0 ) are consecutive with respect to M0 , iff no other vertex of S(M0 ) lies between s
and s0 on R0 . We say that M0 has the distance property iff for every pair s, s0 ∈ S(M0 ) of vertices
that are consecutive with respect to M0 , NM0 (s, s0 ) < d(s, s0 )/4.
We first show that there is a large subset of the demand pairs in M0 with the distance property in
the following lemma, whose proof appears in the next subsection.
Lemma 5.5 With probability at least 1/2 over the construction of Î, there is a subset M0 ⊆ M0 of
demand pairs that has the distance property, and |M0 | = Ω(|M0 |/ log3 M ).
Finally, we show that every set M0 of demand pairs with the distance property can be routed via
spaced-out paths.
Lemma 5.6 Assume that M0 ⊆ M0 is a subset of demand pairs that has the distance property. Then
there is a spaced-out set P of paths routing all pairs of M0 in graph Ĝ.
The above two lemmas finish the proof of Theorem 5.5, since |M0 | = β ∗ (I). We prove these lemmas
in the following two subsections.
5.2.1

Proof of Lemma 5.5

We assume that |M0 | > c log3 M for some large enough constant c, since otherwise we can return a
set M0 containing a single demand pair. We gradually modify the set M0 of the demand pairs, by
selecting smaller and smaller subsets M1 , M2 , M3 , and M0 . For each vertex vertex v ∈ V1 ∪ V2 of
the (r,h)-GPwB instance G̃, let δ(v) denote the set of all edges of E(G̃) incident to v.
We start by performing two “regularization” steps on the vertices of V2 and V1 respectively. Intuitively,
we will select two integers p and q, and a large enough subset M2 ⊆ M0 of demand pairs, so that
for every vertex vi ∈ V1 , either no demand pair in M2 has its source on Ki , or roughly 2p of them
do. Similarly, for every vertex vj0 ∈ V2 , either no demand pairs in M2 has its destination on Kj0 , or
roughly 2q of them do. We will not quite achieve this, but we will come close enough.
Step 1 [Regularizing the degrees in V2 ]. In this step we select a large subset M1 ⊆ M0 of
the demand pairs, and an integer q, such that, for each vertex v ∈ V2 , the number of edges of E(G̃)
incident to v, whose corresponding demand pair lies in M1 , is either 0, or roughly 2q . In order to do
this, we partition the vertices of V2 into classes Z1 , . . . , Zdlog M e , where a vertex v 0 ∈ V2 belongs to class
23

Zy iff 2y−1 ≤ |E 0 ∩ δ(v 0 )| < 2y . If v ∈ Zy , then we say that all edges in δ(v) ∩ E 0 belong to the class
Zy . Therefore, each edge of E 0 belongs to exactly one class, and there is some index 1 ≤ q ≤ dlog M e,
such that at least Ω(|M0 |/ log M ) edges of E 0 belong to class Zq . We let E 1 ⊆ E 0 be the set of all
edges that belong to the class Zq , and we let M1 = M(E 1 ) ⊆ M0 be the corresponding subset of the
demand pairs.
Step 2 [Regularizing the degrees in V1 ]. This step is similar to the previous step, except that
it is now performed on the vertices of V1 . We partition the vertices of V1 into classes Y1 , . . . , Ydlog M e ,
where a vertex v ∈ V1 belongs to class Yz iff 2z−1 ≤ |E 1 ∩ δ(v)| < 2z . If v ∈ Yz , then we say that
all edges in δ(v) ∩ E 1 belong to the class Yz . As before, every edge of E 1 belongs to exactly one
class, and there is some index 1 ≤ p ≤ dlog M e, such that at least Ω(|E 1 |/ log M ) ≥ Ω(|M0 |/ log2 M )
edges of E 1 belong to the class Yp . We let E 2 ⊆ E 1 denote the set of all edges that belong to
class Yp , and M2 = M(E 2 ) ⊆ M1 denote the corresponding subset of the demand pairs, so that
|M2 | = Ω(|M0 |/ log2 M ).
Notice that so far, for every vertex v ∈ V1 , if δ(v) ∩ E 2 6= ∅, then 2p−1 ≤ |δ(v) ∩ E 2 | < 2p . However, for
a vertex v ∈ V2 with δ(v) ∩ E 2 6= ∅, we are only guaranteed that |δ(v) ∩ E 2 | < 2q , since we may have
discarded some edges that were incident to v from E 1 . Moreover, the subset M2 of the demand pairs
is completely determined by the solution ((W1 , . . . , Wr ), (E1 , . . . , Er )) to the (r,h)-GPwB problem, and
is independent of the random choices made in our construction of the NDP-Grid problem instance.
The following observation will be useful for us later.
Observation 5.7 h ≥ 2p · 2q /4.
Proof: From our assumption that |M0 | > c log3 M , E 2 6= ∅. Therefore, there must be an index
1 ≤ i ≤ r with Ei ∩ E 2 6= ∅. Fix any such index i. Then there is a vertex vj0 ∈ Wi ∩ V2 , such
that at least one edge of δ(vj0 ) belongs to E 2 . But then, from the definition of E 2 , at least 2q−1
edges of δ(vj0 ) belong to E 2 . Assume without loss of generality that these edges connect vj0 to vertices
v1 , . . . , v2q−1 ∈ V1 . All these vertices must also belong to Wi , and for each 1 ≤ x ≤ 2q−1 , vertex vx
has at least one edge in δ(vx ) ∩ E 2 . From our definition of E 2 and E 1 , at least 2p−1 edges of δ(vx )
belonged to E 1 . Therefore, |E 1 ∩ Ei | ≥ 2q−1 · 2p−1 . But |Ei | ≤ h, and so h ≥ 2p · 2q /4.
For each vertex vi ∈ V1 , let Xi ⊆ V (Ki ) be the set of all vertices that serve as the sources of the
demand pairs in M, so Xi = S(M)
l ∩ V (K
m i ). Recall that |Xi | = β(vi ), and every pair of vertices
h log M
in Xi is separated by at least 512 β(vi ) vertices of Ki . We let Xi0 ⊆ Xi denote the subset of
2
vertices that
j serve2 asksources of the demand pairs in M . We say that a sub-path Q ⊆ Ki is heavy iff
M
|V (Q)| = 512h 2log
, and |V (Q) ∩ Xi0 | > 16 log M .
p

Observation 5.8 With probability at least 0.99 over the choice of the random permutation ρ0 , for all
vi ∈ V1 , no heavy sub-path Q ⊆ Ki exists.
Proof: Since |V1 | ≤ M , from the union bound, it is enough to prove that for a fixed vertex vi ∈ V1 ,
the probability that a heavy sub-path Q ⊆ Ki exists is at most 1/(100M ). We now fix some vertex
vi ∈ V1 . Observe that Ki may only contain a heavy sub-path if β(vi ) = |Xi | ≥ 16 log M . We call the
vertices of Xi0 pink, and the remaining vertices of Xi yellow. Let P denote the number of the pink
vertices. Then 2p−1 ≤ P < 2p . Let µ = 4 log M , and let Ei be the bad event that there is a set of
b|Xi |µ/P c consecutive vertices of Xi , such that at least 4µ of them are pink.
Observe that the selection of the pink vertices only depends on the solution to the (r,h)-GPwB problem,
and is independent of our construction of the NDP-Grid instance. The ordering of the vertices in Xi is
24

determined by the permutation ρ0 of U2 , and is completely random. Therefore, from Lemma 5.3, the
probability of Ei is at most |Xi |/4µ ≤ M/44 log M ≤ 1/M 7 .
Let Ei0 be the event that some sub-path Q of Ki is heavy. We claim that Ei0 may only happen if event
Ei happens.
m
k consider some sub-path Q of Ki , and assume that it is heavy. Recalll that Q
j Indeed,
512h log2 M
h log M
vertices.
Since
every
pair
of
vertices
in
X
is
separated
by
at
least
512
contains
i
2p
β(vi )
vertices, we get that:




512h log2 M/2p
|Xi |µ
β(vi ) log M
+1≤
,
|V (Q) ∩ Xi | ≤
+1≤
512 dh log M/β(vi )e
2p
P
as 2p−1 ≤ P < 2p . Since Q is heavy, at least 4µ = 16 log M of the vertices of V (Q) ∩ Xi belong to Xi0 ,
that is, they are pink. Therefore, there is a set of b|Xi |µ/P c consecutive vertices of Xi , out of which
4µ are pink, and Ei happens. We conclude that Pr [Ei0 ] ≤ Pr [Ei ] ≤ 1/M 7 , and overall, since we have
assumed that M > 250 , the probability that a heavy path exists in any block Ki is bounded by 0.99
as required.
Let Ebad be the bad event that for some vi ∈ V1 , block Ki contains a heavy path. From Observation 5.8,
the probability of Ebad is at most 0.01.
The following claim will be used to bound the values NM2 (s, s0 ).
Claim 5.9 Consider some vertex vj ∈ V1 in graph G̃, and the block Kj representing it. Then with
probability at least (1 − 1/M 3 ), for every pair s, s0 ∈ S(M2 ) ∩ V (Kj ) of source vertices that are
consecutive with respect to M2 , NM2 (s, s0 ) ≤ 128h log M/2p .
Proof: Fix some vertex vj ∈ V1 and consider the block Kj representing it. Assume that vj belongs
to the cluster Wi in our solution to the (r,h)-GPwB problem. Let s, s0 ∈ S(M2 ) ∩ V (Kj ) be a pair
of source vertices that are consecutive with respect to M2 . Recall that we have defined a subset
Ji ⊆ T (M2 ) of destination vertices, that appear consecutively in the ordering σM2 , and contain all
vertices of T (M2 ), that lie in blocks Kj0 0 , whose corresponding vertices vj 0 ∈ V2 ∩ Wi .
Let A = Wi ∩ V2 ; let A0 ⊆ A contain all vertices that have an edge of E 2 ∩ Ei incident to them; and let
A00 ⊆ A0 contain all vertices that have an edge of E 2 ∩ Ei connecting them to vj . Since the solution
to the (r,h)-GPwB problem instance is perfect, every vertex of A (and hence A0 and A00 ) belongs to
a distinct group of U ∈ U2 . We denote by U 0 ⊆ U2 the set of all groups to which the vertices of A0
belong, and we define U 00 ⊆ U 0 similarly for A00 . Consider now some group U ∈ U 0 , and let va0 be the
unique vertex of U that belongs to A0 . We denote by C(U ) the set of all vertices of the corresponding
block Ka0 that belong to T (M2 ). Therefore, we now obtain a partition {C(U )}U ∈U 0 of all vertices of
Ji into subsets, where each subset contains at most 2q vertices. Moreover, in the ordering σM2 , the
vertices of each such set C(U ) appear consecutively, in the order of their appearance on R00 , while the
ordering between the different sets C(U ) is determined by the ordering of the corresponding groups
U in ρ0 . Let ρ00 be the ordering of the groups in U 0 induced by ρ0 , so that ρ00 is a random ordering of
U 0 . Observe that, since the choice of the set M2 is independent of the ordering ρ0 (and only depends
on the solution to the (r,h)-GPwB problem instance), so is the choice of the sets U 0 and U 00 .
Let t and t0 be the destination vertices that correspond to s and s0 , respectively, that is, (s, t), (s0 , t0 ) ∈
M2 . Assume that t ∈ Kz0 and t0 ∈ Kz0 0 , where vz0 and vz0 0 are vertices of V2 . From our definition,
both vz0 and vz0 0 must belong to the set A00 . Assume that vz0 belongs to the group U 0 in U2 , while vz0 0
belongs to group U 00 . Again, from our definitions, both U 0 , U 00 ∈ U 00 . From the above discussion, if the
number of groups U ∈ U 0 that fall between U 0 and U 00 is γ, then the number of destination vertices
lying between t and t0 in σM2 is at most 2q · (γ + 2). Therefore, it is now enough to bound the value of
25

γ. In order to do so, we think of the groups of U 00 as pink, and the remaining groups of U 0 as yellow.
Let P denote the total number of all pink groups, and let n∗ = |U 0 |. From the construction of M2 ,
P = |S(M2 ) ∩ V (Kj )| ≥ 2p−1 . We use the following observation to upper-bound n∗ .
Observation 5.10 n∗ ≤ h/2q−1 .
Proof: Since we have started with a perfect solution to I, for each group U ∈ U 0 , there is exactly one
vertex of U in Wi . Due to Step 1 of regularization, each such vertex contributed at least 2q−1 edges
to E 1 ∩ Ei , while |E 1 ∩ Ei | ≤ h. Therefore, n∗ ≤ h/2q−1 .
Let µ = 4 log M , and let EY be the event that there are at least d4n∗ µ/P e consecutive yellow groups
in the ordering ρ00 of U 0 . From Lemma 5.2, the probability of EY is at most n∗ /eµ ≤ M/eµ ≤ 1/M 3 .
If event EY does not happen, then the length of the longest consecutive sub-sequence of ρ00 containing
only yellow groups is bounded by:



4n∗ µ
64h log M
≤
.
P
2q 2p

Assume now that EY does not happen, and consider any two vertices s, s0 ∈ S(M2 ) ∩ V (Kj ) that are
consecutive with respect to M2 . Assume that their corresponding destination vertices are t and t0
respectively, and that t and t0 belong to the groups U and U 0 , respectively. Then U and U 0 are pink
groups. Moreover, since the ordering of the vertices of S(M) ∩ V (Kj ) on R0 is identical to the ordering
of the groups of U 00 to which their destinations belong in ρ0 , no other pink group appears between U
M
and U 0 in ρ00 . Therefore, at most 64h2qlog
groups of U 0 lie between U and U 0 in ρ00 . Recall that for
2p
00
0
0
each group U ∈ U , at most one vertex vz ∈ U 00 belongs to Wi , and that the corresponding block Kz0
may contribute at most 2q destination vertices to T (M2 ). We conclude that the number of vertices
separating t from t0 in σM3 is bounded by:



64h log M
128h log M
+ 2 · 2q ≤
.
q
p
2 2
2p

(We have used Observation 5.7). Therefore, if event EY does not happen, then for every pair s, s0 ∈
M
S(M2 ) ∩ V (Kj ) of vertices that are consecutive with respect to M2 , NM2 (s, s0 ) ≤ 128h2log
.
p
0
be the bad event that for some vertex vj ∈ V1 , for some pair s, s0 ∈ S(M2 ) ∩ V (Kj ) of source
Let Ebad
vertices that are consecutive with respect to M2 , NM2 (s, s0 ) > 128h log M/2p . By applying the Union
0
Bound to the result of Claim 5.9, we get that the probability of Ebad
is at most 1/M 2 . Notice that
0
the probability that neither Ebad nor Ebad
happen is at least 1/2. We assume from now on that this is
indeed the case, and show how to compute a large subset M0 ⊆ M2 of the demand pairs that has the
distance property. This is done in the following two steps.


Step 3 [Sparsifying the Sources.] Assume that M2 = (s1 , t1 ), . . . , (s|M2 | , t|M2 | ) , where the
demand pairs are indexed according to the left-to-right ordering of their sources on R0 , that is
s1 , s2 , . . . , s|M2 | appear on R0 in this order. We now define:
M3 = {(si , ti ) | i = 1

mod d32 log M e} .

Let E 3 ⊆ E 2 be the set of edges of G̃ whose corresponding demand pairs belong to M3 . It is easy to
verify that |M3 | ≥ Ω(|M2 |/ log M ) = Ω(|M0 |/ log3 M ).
We also obtain the following claim.
26

0
Claim 5.11 Assume that events Ebad and Ebad
did not happen. Then for each 1 ≤ j ≤ N1 , for every
0
3
pair s, s ∈ S(M ) ∩ V (Kj ) of source vertices, NM3 (s, s0 ) ≤ 128d(s, s0 ).

Proof: Fix some 1 ≤ j ≤ N1 , and some pair s, s0 ∈ S(M3 )∩V (Kj ) of vertices. Let S 0 = {s1 , s2 , . . . , sz }
be the set of all vertices of S(M2 ) that appear between s and s0 on R0 . Assume w.l.o.g. that s lies to
the left of s0 on R0 , and denote s0 = s and sz+1 = s0 . Assume further that the vertices of S 0 are indexed
according to their left-to-right ordering on R0 . Note that, from the definition of M3 , z ≥ d32 log M e
must hold.


Let I ⊆ Kj be the sub-path of Kj between s and s0 . We partition I into paths containing 512h log2 M/2p
vertices each, except for the
may be heavy,
j last path
k that may contain fewer vertices. Since no such path


z
0
we obtain at least n = 16 log M disjoint sub-paths of I, each of which contains 512h log2 M/2p
vertices. We conclude that:
0

0



d(s, s ) ≥ n · 512h log2 M/2p − 1 ≥



z
16 log M





2zh log M
· 512h log2 M/2p − 1 ≥
.
2p

On the other hand, since σM3 is the same as the ordering of T (M3 ) induced by σM2 , we get that:
0

0

NM3 (s, s ) ≤ NM2 (s, s ) ≤

z
X

NM2 (si , si+1 ) ≤ (z + 1) ·

i=0

128h log M
≤ 128d(s, s0 ).
2p

Step 4 [Decreasing the Values NM3 (s, s0 )]. We are now ready to define the final set M0 ⊆ M3
of demand pairs.

Assume that M3 = (s1 , t1 ), . . . , (s|M3 | , t|M3 | ) , where the demand pairs are indexed according to the
ordering of their destinations in σM3 (notice that this is the same as the ordering of T (M3 ) induced
by σM2 ). We now define:
M0 = {(si , ti ) | i = 1

mod 512} .

We claim that M0 has the distance property. Indeed, consider any two pairs (s, t), (s0 , t0 ) ∈ M0 ,
such that s and s0 are consecutive with respect to M0 . If s and s0 lie in different blocks Kj , then,
since the distance between any such pair of blocks is at least 10M , while |M0 | ≤ M , we get that
NM0 (s, s0 ) ≤ d(s, s0 )/4. Otherwise, both s and s0 belong to the same block Kj . But then it is easy
to verify that NM0 (s, s0 ) ≤ NM3 (s, s0 )/512 ≤ d(s, s0 )/4 from Claim 5.11. We conclude that with
0
probability at least 1/2, neither of the events Ebad , Ebad
happens, and in this case, M0 has the distance
property.
5.2.2

Proof of Lemma 5.6

Recall that R0 and R00 are the rows of Ĝ containing the vertices of S(M) and T (M) respectively,
and that R0 and R00 lie at distance at least `/4 form each other and from the top and the bottom
boundaries of Ĝ, where ` > M 2 is the dimension of the grid. Let R be any row lying between R0 and
R00 , within distance at least `/16 from each of them.
We denote M 0 = |M0 |, and M0 = {(s1 , t1 ), . . . , (sM 0 , tM 0 )}, where the pairs are indexed according to
the ordering of their destination vertices in σM0 . To recap, the ordering σM0 of T (M0 ) was defined
27

as follows. We have defined a partition (J1 , . . . , Jr ) of the vertices of T (M0 ) into subsets, where each
set Ji represents a cluster Wi in our solution to the (r,h)-GPwB problem instance, and contains all
destination vertices t ∈ T (M0 ) that lie in blocks Kj0 , for which the corresponding vertex vj ∈ V2
belongs to Wi . The ordering of the destination vertices inside each set Ji is the same as their ordering
on R00 , and the different sets J1 , . . . , Jr are ordered in the order of their indices.
Let X = {xi | 1 ≤ i ≤ M 0 } be a set of vertices of R, where xi is the (2i)th vertex of R from the left.
We will construct a set P ∗ of spaced-out paths routing all demand pairs in M0 , so that the path Pi
routing (si , ti ) intersects the row R at exactly one vertex — the vertex xi . Notice that row R partitions
the grid Ĝ into two sub-grids: a top sub-grid Gt spanned by all rows that appear above R (including
R), and a bottom sub-grid Gb spanned by all rows that appear below R (including R).
It is now enough to show that there are two sets of spaced-out paths: set P 1 routing all pairs in
{(si , xi ) | 1 ≤ i ≤ M 0 } in the top grid Gt , and set P 2 routing all pairs in {(ti , xi ) | 1 ≤ i ≤ M 0 } in the
bottom grid Gb , so that both sets of paths are internally disjoint from R.
Routing in the Top Grid. Consider some vertex vj ∈ V1 , and the corresponding block Kj . We
construct a sub-grid K̂j of Ĝ, containing Kj , that we call a box, as follows. Let Cj be the set of all
columns of Ĝ intersecting Kj . We augment Cj by adding 2M columns lying immediately to the left
and 2M columns lying immediately to the right of Cj , obtaining a set Cˆj of columns. Let R̂ contain
three rows: row R0 ; the row lying immediately above R0 ; and the row lying immediately below R0 .
Then box K̂j is the sub-grid of Ĝ spanned by the rows in R̂ and the columns in Cˆj . Since every block is
separated by at least 10M columns from every other block, as well as the left and the right boundaries
of Ĝ, the resulting boxes are all disjoint, and every box is separated by at least 2M columns of Ĝ from
every other box, and from the left and the right boundaries of Ĝ.
We will initially construct a set P 1 of spaced-out paths in Gt , such that each path Pi ∈ P 1 , for
1 ≤ i ≤ M 0 , originates from the vertex xi , and visits the boxes K̂1 , K̂2 , . . . , K̂N1 in turn. We will
ensure that each such path Pi contains the corresponding source vertex si . Eventually, by suitably
truncating each such path Pi , we will ensure that it connects xi to si .
Claim 5.12 Consider some vertex vj ∈ V1n
, and the corresponding
box K̂j . Denote Yj = S(M0 ) ∩
o
V (Kj ), Mj = |Yj |, and assume that Yj = si1 , si2 , . . . , siMj , where the indexing of the vertices of
Yj is consistent with the indexing of the vertices of S(M0 ) that we have defined above, and i1 < i2 <
. . . < iMj . Then there is a set Wj of M 0 columns of the box K̂j , such that:
• set Wj does not contain a pair of consecutive columns; and
• for each 1 ≤ z ≤ Mj , the iz th column of Wj from the left contains the source vertex siz .
Proof: Observe that from Observation 5.1, the vertices si1 , si2 , . . . , siMj must appear in this left-toright order on R0 , while the vertices xi1 , xi2 , . . . , xiMj appear in this left-to-right order on R. Moreover,
for all 1 ≤ z < Mj , iz+1 − iz − 1 = NM0 (siz , siz+1 ) ≤ d(siz , siz+1 )/4. We add to Wj all columns of K̂j
where the vertices of Yj lie. For each 1 ≤ z < Mj , we also add to Wj an arbitrary set of (iz+1 − iz − 1)
columns lying between the column of siz and the column of siz+1 , so that no pair of columns in Wj
is consecutive. Finally, we add to Wj (i1 − 1) columns that lie to the left of the column of si1 , and
(M 0 − iMj ) columns that lie to the right of the column of siMj . We make sure that no pair of columns
in Wj is consecutive – it is easy to see that there are enough columns to ensure that.

28

Claim 5.13 There is a set P 1 = {P1 , . . . , PM 0 } of spaced-out paths in Gt , that are internally disjoint
from R, such that for each 1 ≤ i ≤ M 0 , path Pi originates from vertex xi , and for all 1 ≤ j ≤ N1 , it
contains the ith column of Wj ; in particular, it contains si .
We defer the proof of the claim to Section C of the appendix; see Figure 4 for an illustration of the
routing.

Figure 4: Routing in the top grid.

Routing in the Bottom Grid. Consider some vertex vj0 ∈ V2 , and the corresponding block Kj0 .
We construct a box K̂j0 containing Kj0 exactly as before. As before, the resulting boxes are all disjoint,
and every box is separated by at least 2M columns of Ĝ from every other box, and from the left and
the right boundaries of Ĝ.
As before, we will initially construct a set P 2 of spaced-out paths in Gb , such that each path Pi0 ∈ P 2 ,
0
for 1 ≤ i ≤ M 0 , originates from the vertex xi , and visits the boxes K̂10 , K̂20 , . . . , K̂N
in turn. We
2
0
will ensure that each such path Pi contains the corresponding destination vertex ti . Eventually, by
suitably truncating each such path Pi0 , we will ensure that it connects xi to ti .
Claim 5.14 Consider some vertex vj0 ∈ V2 , and the corresponding box K̂j0 . Denote Yj0 = T (M0 ) ∩
n
o
V (Kj0 ), Mj0 = |Yj0 |, and assume that Yj0 = ti1 , ti2 , . . . , tiMj , where the indexing of the vertices of Yj0
is consistent with the indexing of the vertices of T (M0 ) that we have defined above, and i1 < i2 <
. . . < iMj0 . Then there is a set Wj0 of M 0 columns of the box K̂j0 , such that:
• set Wj0 does not contain a pair of consecutive columns; and
• for each 1 ≤ z ≤ Mj0 , the iz th column of Wj0 from the left contains the destination vertex tiz .
Proof: From our construction of σM0 , the vertices ti1 , ti2 , . . . , tiMj appear consecutively in this order
in σM0 . Moreover, from the construction of M, every pair of these destination vertices is separated
by at least one vertex. We add to Wj0 all columns in which the vertices ti1 , ti2 , . . . , tiMj lie. We also
add to Wj0 i1 − 1 columns that lie to the left of the column of ti1 , and M 0 − iMj0 columns that lie to
the right of the column of tiMj in K̂j0 . We make sure that no pair of columns in Wj0 is consecutive – it
is easy to see that there are enough columns to ensure that.
The proof of the following claim is identical to the proof of Claim 5.13 and is omitted here.
29


0
Claim 5.15 There is a set P 2 = P10 , . . . , PM
of spaced-out paths in Gb , that are internally disjoint
0
0
0
from R, such that for each 1 ≤ i ≤ M , path Pi originates from vertex xi , and for all 1 ≤ j ≤ N2 , it
contains the ith column of Wj0 ; in particular it contains ti

∗
By combining the paths in sets P 1 and P 2 , we obtain a new set P ∗ = P1∗ , . . . , PM
of spaced-out
0
0
∗
paths, such that for all 1 ≤ i ≤ M , path Pi contains si , xi and ti . By suitably truncating each such
path, we obtain a collection of spaced-out paths routing all demand pairs in M0 .

5.3

From Routing to Partitioning

The goal of this subsection is to prove the following theorem, that will complete the proof of Theorem 3.2.
Theorem 5.16 There is a deterministic efficient algorithm, that, given a valid instance I = (G̃ =
(V1 , V2 , E), U1 , U2 , h, r) of the (r,h)-GPwB problem with |E| = M , the corresponding (random) instance
Î of NDP-Grid, and a solution P ∗ to Î, computes a solution to the (r,h)-GPwB instance I of value at
least Ω(|P ∗ |/ log3 M ).
Let M∗ ⊆ M be the set of the demand pairs routed by the solution P ∗ , and let E ∗ ⊆ E be the set
of all edges e, whose corresponding demand pair belongs to M∗ . Let G̃0 ⊆ G̃ be the sub-graph of G̃
induced by the edges in E ∗ . Notice that whenever two edges of G̃ belong to the same bundle, their
corresponding demand pairs share a source or a destination. Since all paths in P ∗ are node-disjoint,
all demand pairs in M∗ have distinct sources and destinations, and so no two edges in E ∗ belong to
the same bundle.
Note that, if |P ∗ | ≤ 264 h log3 M , then we can return the solution ((W1 , . . . , Wr ), (E1 , l. . . , Er )), mwhere
∗|
≤h
W1 = V (G̃) and W2 = W3 = · · · = Wr = ∅; set E1 contains an arbitrary subset of 264|P
log3 M
∗
∗
edges of E , and all other sets Ei are empty. Since no two edges of E belong to the same bundle,
we obtain a feasible solution to the (r,h)-GPwB problem instance of value Ω(|P ∗ |/ log3 M ). Therefore,
from now on, we assume that |P ∗ | > 264 h log3 M .
Our algorithm computes a solution to the (r,h)-GPwB instance I by repeatedly partitioning G̃0 into
smaller and smaller sub-graphs, by employing suitably defined balanced cuts.
Recall that, given a graph H, a cut in H is a bi-partition (A, B) of its vertices. We denote by EH (A, B)
the set of all edges with one endpoint in A and another in B, and by EH (A) and EH (B) the sets of
all edges with both endpoints in A and in B, respectively. Given a cut (A, B) of H, the value of the
cut is |EH (A, B)|. We will omit the subscript H when clear from context.
Definition 6 Given a graph H and a parameter 0 < ρ < 1, a cut (A, B) of H is called a ρ-edgebalanced cut iff |E(A)|, |E(B)| ≥ ρ · |E(H)|.
The following theorem is central to the proof of Theorem 5.16.
Theorem 5.17 There is an efficient algorithm, that, given a vertex-induced subgraph H of G̃0 with
|E(H)|
|E(H)| > 264 h log3 M , computes a 1/32-edge-balanced cut of H, of value at most 64
log M .
We prove Theorem 5.17 below, after we complete the proof of Theorem 5.16 using it. Our algorithm
maintains a collection G of disjoint vertex-induced sub-graphs of G̃0 , and consists of a number of
phases. The input to the first phase is the collection G containing a single graph - the graph G̃0 . The
30

algorithm continues as long as G contains a graph H ∈ G with |E(H)| > 264 · h log3 M ; if no such
graph H exists, the algorithm terminates. Each phase is executed as follows. We process every graph
H ∈ G with |E(H)| > 264 · h log3 M one-by-one. When graph H is processed, we apply Theorem 5.17
|E(H)|
to it, obtaining a 1/32-edge-balanced cut (A, B) of H, of value at most 64
log M . We then remove H
from G, and add H[A] and H[B] to G instead. This completes the description of the algorithm. We
use the following claim to analyze it.
ClaimP5.18 Let G 0 be the final set of disjoint sub-graphs of G̃0 obtained at the end of the algorithm.
Then H∈G 0 |E(H)| ≥ Ω(|E(G̃0 )|), and |G 0 | ≤ r.
Proof: We construct a binary partitioning tree τ of graph G̃0 , that simulates the graph partitions
computed by the algorithm. For every sub-graph H ⊆ G̃0 that belonged to G over the course of the
algorithm, tree τ contains a vertex v(H). The root of the tree is the vertex v(G̃0 ). If, over the course
of our algorithm, we have partitioned the graph H into two disjoint vertex-induced sub-graphs H0 and
H00 , then we add an edge from v(H) to v(H0 ) and to v(H00 ), that become the children of v(H) in τ .
The level of a vertex v(H) in the tree is the length of the path connecting v(H) to the root of the
tree; so the root of the tree is at level 0. The depth of the tree, that we denote by ∆, is the length
of the longest leaf-to-root path in the tree. Since the cuts computed over the course of the algorithm
M
are 1/32−edge-balanced, ∆ ≤ loglog
(32/31) . Consider now some level 0 ≤ i ≤ ∆, and let Vi be the set
S
of all vertices of the tree τ lying at level i. Let Êi = v(H)∈Vi E(H) be the set of all edges contained
in all sub-graphs of G̃0 , whose corresponding vertex belongs to level i. Finally, let mi = |Ei |. Then
m0 = |E(G̃0 )|, and for all 1 ≤ i ≤ ∆, the number of edges discarded over the course of phase i is
mi−1 − mi ≤ mi−1 /(64 log M ) ≤ m0 /(64 log M ) — this is since, whenever we partition a graph H into
two subgraphs, we lose at most |E(H)|/(64 log M ) of its edges. Overall, we get that:
m0 − m∆ ≤

∆m0
log M
m0
m0
≤
·
≤
,
64 log M
log 32/31 64 log M
2

P
and so H∈G 0 |E(H)| = m∆ ≥ m0 /2. This finishes the proof of the first assertion. We now turn to
prove the secondPassertion.  Recall that no two edges of E ∗ may belongP
to the same bundle. Since
0 ⊆ E ∗ of edges, |E 0 | ≤
h = β ∗ (I)/r =
β(v)
/r,
for
any
subset
E
v∈V1
v∈V1 β(v) ≤ hr must hold,
∗
and in particular, |E | ≤ hr. It is now enough to prove that for every leaf vertex v(H) of τ , |E(H)| ≥ h
— since all graphs in G 0 are mutually disjoint, and each such graph corresponds to a distinct leaf of
τ , this would imply that |G 0 | ≤ r.
Consider now some leaf vertex v(H) of τ , and let v(H0 ) be its parent. The |E(H0 )| ≥ 264 h log3 M ,
and, since the partition of H0 that we have computed was 1/32-balanced, |E(H)| ≥ |E(H0 )|/32 ≥ h.
We conclude that |G 0 | ≤ r.
We are now ready to define the solution ((W1 , . . . , Wr ), (E1 , . . . , Er )) to the (r,h)-GPwB problem instance I. Let G 0 be the set of the sub-graphs of G̃0 obtained at the end of our algorithm, and denote
G 0 = {H1 , H2 , . . . , Hz }. Recall that from Claim 5.18, z ≤ r. For 1 ≤ i ≤ z, we let Wi = V (Hi ). If
|E(Hi )| ≤ h, then we let Ei = E(Hi ); otherwise, we let Ei contain any subset of h edges of E(Hi ).
Since |E(Hi )| ≤ 264 h log3 M , in either case, |Ei | ≥ Ω(|E(Hi )|/ log3 M ). For i > z, we set Wi = ∅ and
Ei = ∅. Since, as observed before, no pair of edges of E ∗ belongs to the same bundle, it is immediate
to verify that we obtain a feasible solution to the (r,h)-GPwB problem instance. The value of the
solution is:
r
X
i=1

|Ei | ≥

r
X

Ω(|E(Hi )|/ log3 M ) = Ω(|E(G̃0 )|/ log3 M ) = Ω(|P ∗ |/ log3 M ),

i=1

31

from Claim 5.18. In order to complete the proof of Theorem 5.16, it now remains to prove Theorem 5.17.
Proof of Theorem 5.17. Let H be a vertex-induced subgraph of G̃0 with |E(H)| > 264 h log3 M .
Our proof consists of two parts. First, we show an efficient algorithm to compute a drawing of H with
relatively few crossings. Next, we show how to exploit this drawing in order to compute a 1/32-edgebalanced cut of H of small value. We start by defining a drawing of a given graph in the plane and
the crossings in this drawing.
Definition 7 A drawing of a given graph H0 in the plane is a mapping, in which every vertex of H
is mapped to a point in the plane, and every edge to a continuous curve connecting the images of its
endpoints, such that no three curves meet at the same point; no curve intersects itself; and no curve
contains an image of any vertex other than its endpoints. A crossing in such a drawing is a point
contained in the images of two edges.
Lemma 5.19 There is an efficient algorithm that, given a solution P ∗ to the NDP-Grid problem
instance Î, and a vertex-induced subgraph H ⊆ G̃0 , computes a drawing of H with at most 2048 ·
|E(H)| dh log M e crossings.
Proof: We think of the grid Ĝ underlying the NDP-Grid instance Î as the drawing board, and map
the vertices of H to points inside some of its carefully selected cells. Consider a vertex vi ∈ V (H) ∩ V1 ,
and let Ki be the block representing this vertex. Let κi be any cell of the grid Ĝ that has a vertex
of Ki on its boundary. We map the vertex vi to a point pi lying in the middle of the cell κi (it is
sufficient that pi is far enough from the boundaries of the cell). For every vertex vj0 ∈ V (H) ∩ V2 , we
select a cell κ0j whose boundary contains a vertex of the corresponding block Kj0 , and map vj0 to a
point p0j lying in the middle of κ0j similarly.
Next, we define the drawings of the edges of E(H). Consider any such edge e = (vi , vj0 ) ∈ E(H), with
vi ∈ V1 and vj0 ∈ V2 , and let (s, t) ∈ M∗ be its corresponding demand pair. Let Ki and Kj0 be the
blocks containing s and t respectively, and let P ∈ P ∗ be the path routing the demand pair (s, t) in
our solution to the NDP-Grid problem instance Î. The drawing of the edge e is a concatenation of
the following three segments: (i) the image of the path P , that we refer to as a type-1 segment; (ii) a
straight line connecting s to the image of vi , that we refer to as a type-2 segment; and (iii) a straight
line connecting t to the image of vi0 , that we refer to as a type-3 segment. If the resulting curve has
any self-loops, then we delete them.
We now bound the number of crossings in the resulting drawing of H. Since the paths in P ∗ are
node-disjoint, whenever the images of two edges e and e0 cross, the crossing must be between the
type-1 segment of e, and either the type-2 or the type-3 segment of e0 (or the other way around).
Consider now some edge e = (vi , vj0 ) ∈ E(H) with vi ∈ V1 and vj0 ∈ V2 , and let Ki and Kj0 be the
blocks representing vi and vj0 respectively. Let (s, t) ∈ M∗ be the demand pair corresponding to e.
Assume that a type-1 segment of some edge e0 crosses a type-2 segment of e. This can only happen
if the path P 0 ∈ P ∗ routing the demand pair (s0 , t0 ) corresponding to the edge e0 contains a vertex of
Ki . Since |V (Ki )| ≤ 1024 · dh log M e, at most 1024 · dh log M e type-1 segments of other edges may
cross the type-2 segment of e. The same accounting applies to the type-3 segment of e. Overall, the
number of crossings in the above drawing is bounded by:
X

2 · 1024 · dh log M e = 2048 · |E(H)| dh log M e .

e∈E(H)

32

Figure 5: Grid Qv obtained from v
Next, we show an efficient algorithm that computes a small balanced partition of any given graph H0 ,
as long as its maximum vertex degree is suitably bounded, and we are given a drawing of H0 with a
small number of crossings.
Lemma 5.20 There is an efficient algorithm that, given any graph H with |E(H)| = m and maximum
vertex degree at most d, and a drawing ϕ of H with at most cr ≤ mdα crossings for some√α > 1, such
that m > 220 dα, computes a 1/32-edge-balanced cut (A, B) of H of value |E(A, B)| ≤ 64 8mdα.
Before we complete the proof of the lemma, we show that the proof of Theorem 5.17 follows from it. Let
m = |E(H)|. Note that the maximum vertex degree in graph H is bounded by maxv∈V1 ∪V2 {β(v)}, as
E(H) cannot contain two edges that belong to the same bundle. From the definition of valid instances,
h ≥ β(v), and so the maximum vertex degree in H is bounded by d = h. From Lemma 5.19, the
drawing ϕ of H has at most 2048|E(H)| dh log M e ≤ 212 md log M crossings. Setting α = 212 log M ,
the number of crossings cr in ϕ is bounded by mdα. Moreover, since m > 264 h log3 M , we get that
m > 220 dα. We can now apply Lemma 5.20 to graph H
qto obtain a 1/32-edge-balanced cut (A, B)
p
√
|E(H)|
with |E(A, B)| ≤ 64 8mdα ≤ 64 215 mh log M ≤ 64 m2 /(249 log2 M ) ≤ 64
log M , since we have
assumed that |E(H)| = m > 264 h log3 M . It now remains to prove Lemma 5.20.
Proof of Lemma 5.20. For each vertex v ∈ V (H), we denote the degree of v in H by dv . We assume
without loss of generality that for all v ∈ V (H), dv ≥ 1: otherwise, we can remove all isolated vertices
from H and then apply our algorithm to compute a 1/32-edge-balanced cut (A, B) in the remaining
graph. At the end we can add the isolated vertices to A or B, while ensuring that the cut remains
1/32-balanced, and without increasing its value.
We construct a new graph Ĥ from graph H as follows. For every vertex v ∈ V (H), we add a (dv × dv )grid Qv to Ĥ, so that the resulting grids are mutually disjoint. We call the edges of the resulting
grids regular edges. Let e1 (v), . . . , edv (v) be the edges of H incident to v, indexed in the clockwise
order of their entering the vertex v in the drawing ϕ of H. We denote by Π(v) = {p1 (v), . . . , pdv (v)}
the set of vertices on the top boundary of Qv , where the vertices are indexed in the clock-wise order
of their appearance on the
S boundary of Qv . We refer to the vertices of Π(v) as the portals of Qv
(see Figure 5). Let Π = v∈V (H) Π(v) be the set of all portals. For every edge e = (u, v) ∈ E(H),
we add a new special edge to graph Ĥ, as follows. Assume that e = ei (v) = ej (u). Then we add
an edge (pi (v), pj (u)) to Ĥ. We think of this edge as the special edge representing e. This finishes
the definition of the graph Ĥ. It is immediate to see that the drawing ϕ of H can be extended to a
drawing ϕ0 of Ĥ without introducing any new crossings, that is, the number of crossings in ϕ0 remains
at most cr. Note that every portal vertex is incident to exactly one special edge, and the maximum
vertex degree in Ĥ is 4. We will use the following bound on |V (Ĥ)|:
Observation 5.21 |V (Ĥ)| ≤ (2m + d)d.
P
Proof: Clearly, |V (Ĥ)| = v∈V (H) d2v . Observe that for every pair a ≥ b ≥ 0 of integers, (a + 1)2 +
(b − 1)2 ≥ a2 + b2 . Since maximum vertex degree in H is bounded by d, the sum is maximized when
33

P
all but possibly one summand are equal to d, and, since v∈H dv = 2m, there are at most d2m/de
summands. Therefore, |V (Ĥ)| ≤ b2m/dc · d2 + d2 ≤ (2m + d)d.
Let Ĥ0 be the graph obtained from Ĥ by replacing every intersection point in the drawing ϕ0 of Ĥ
with a vertex. Then Ĥ0 is a planar graph with |V (Ĥ0 )| ≤ |V (Ĥ)| + cr ≤ (2m + d)d + mdα ≤ 4mdα,
as α ≥ 1. We assign weights to the vertices of Ĥ0 as follows: every vertex of Π is assigned the weight
1, and every other vertex is assigned the weight 0. Note that the weight of a vertex is exactly the
number of special edges incident to it, and the total weight of all vertices is W = |Π| = 2m. We will
use the following version of the planar separator theorem [Ung51, LT79, AST94].
Theorem 5.22 ([LT79]) There is an efficient algorithm, that, given a planar graph G = (V, E)
+
with
P n vertices, and an assignment w : V → R of non-negative weights to the vertices of G, with
v∈V w(v) = W , computes a partition (A, X, B) of V (G), such that:
• no edge connecting a vertex of A to a vertex of B exists in G;
P
P
•
v∈A w(v),
v∈B w(v) ≤ 2W/3; and
√
• |X| ≤ 2 2n.
q
We apply Theorem 5.22 to graph Ĥ0 , to obtain a partition (A, X, B) of V (Ĥ0 ), with |X| ≤ 2 2|V (Ĥ0 )| ≤
√
P
P
2 8mdα. Since W = v∈V (Ĥ0 ) w(v) = 2m, we get that |A ∩ Π| = v∈A w(v) ≤ 2W/3 ≤ 4m/3, and
similarly |B ∩ Π| ≤ 4m/3. Assume without loss of generality that |A ∩ Π| ≤ |B √
∩ Π|. We obtain a
bi-partition (A0 , B 0 ) of V (Ĥ0 ) by setting A0 = A ∪ X and B 0 = B. Since |X| ≤ 2 8mdα ≤ m/3 (as
0
m > 220 dα), we are guaranteed that |A0 ∩ Π|,
√ |B ∩ Π| ≤ 4m/3 holds. Moreover, as all vertex degrees
0
0
0
in Ĥ are at most 4, |E(A , B )| ≤ 4|X| ≤ 8 8mdα.
Unfortunately, the cut (A0 , B 0 ) of Ĥ 0 does not directly translate into a balanced cut in H, since for
some vertices v ∈ V (H), the corresponding grid Qv may be split between A0 and B 0 . We now show
how to overcome this difficulty, by moving each such grid entirely to one of the two sides. Before we
proceed, we state a simple fact about grid graphs.
Observation 5.23 Let z > 1 be an integer, and let Q be the (z × z)-grid. Let U be the set of
vertices lying on the top row of Q, and let (X, Y ) be a bi-partition of V (Q). Then |EQ (X, Y )| ≥
min {|U ∩ X|, |U ∩ Y |}.
Proof: It is easy to verify that for any bi-partition (X 0 , Y 0 ) of U into two disjoint subsets, there is
a set P of min {|X 0 |, |Y 0 |} node-disjoint paths in Q connecting vertices of X 0 to vertices of Y 0 . The
observation follows from the maximum flow – minimum cut theorem.
We say that a vertex v ∈ V (H) is split by the cut (A0 , B 0 ) iff V (Qv ) ∩ A0 and V (Qv ) ∩ B 0 6= ∅. We say
that it is split evenly iff |Π(v) ∩ A0 |, |Π(v) ∩ B 0 | ≥ dv /8; otherwise we say that it is split unevenly. We
modify the cut (A0 , B 0 ) in the following two steps, to ensure that no vertex of V (H) remains split.
Step 1 [Unevenly split vertices]. We process each vertex v ∈ V (H) that is unevenly split oneby-one. Consider any such vertex v. If |Π(v) ∩ A0 | > |Π(v) ∩ B 0 |, then we move all vertices of Qv
to A0 ; otherwise we move all vertices of Qv to B 0 . Assume without loss of generality that the former
happens. Notice that from Observation 5.23, |E(A0 , B 0 )| does not increase, since E(Qv ) contributed at
least |Π(v) ∩ B 0 | regular edges to the cut before the current iterations. Moreover, |Π(v) ∩ A0 | increases
by the factor of at most 8/7. Therefore, at the end of this procedure, once√all unevenly split vertices
32
of H are processed, |A0 ∩ Π|, |B 0 ∩ Π| ≤ 78 · 43 m = 21
m and |E(A0 , B 0 )| ≤ 8 8mdα.
34

Step 2 [Evenly split vertices]. In this step, we process each vertex v ∈ V (H) that is evenly split
one-by-one. Consider an iteration where some such vertex v ∈ V (H) is processed. If |A0 ∩Π| ≤ |B 0 ∩Π|,
then we move all vertices of Qv to A0 ; otherwise we move them to B 0 . Assume without loss of generality
that the former happened. Then before the current iteration |A0 ∩ Π| ≤ |Π|/2 ≤ m, and, since
32
0
|Γ(v)| ≤ d < m/21, |A0 ∩ Π| ≤ 32
21 m, while |B ∩ Π| ≤ 21 m as before. Moreover, from Observation 5.23,
before the current iteration, the regular edges of Qv contributed at least d(v)/8 edges to E(A0 , B 0 ),
and after the current iteration, no regular edges of Qv contribute to the cut, but we may have added
up to d(v) new special edges to it. Therefore, after all vertices of H that
√ are evenly split are processed,
0
0
|E(A , B )| grows by the factor of at most 8, and remains at most 64 8mdα.
We are now ready to define the final cut (A∗ , B ∗ ) in graph H. We let A∗ contain all vertices v ∈ V (H)
with V (Qv ) ⊆ A0 , √
and we let B ∗ contain all remaining vertices of V (H). Clearly, |EH (A∗ , B ∗ )| ≤
0
0
|EĤ0 (A , B )| ≤ 64 8mdα. It remains to show that |EH (A∗ )|, |EH (B ∗ )| ≥ |E(H)|/32. We show
∗
that
the P
proof that |EH (B ∗ )| ≥ |E(H)|/32
is symmetric. Observe that
P |EH (A )| 0≥ |E(H)|/32;
P
32m
32m
10m
d
=
|B
∩
Π|
≤
,
while
d
=
2m.
Therefore,
∗
∗
v
v∈B
v∈V (H) v
v∈A dv ≥ 2m − 21 = 21 . But
21
p
√
|EH (A∗ , B ∗ )| ≤ 64 8mdα ≤ 64 m2 /217 < m/4 (since m > 220 dα). Therefore,
∗

|EH (A )| =

P

v∈A∗

dv − |EH (A∗ , B ∗ )|
5m m
m
≥
−
≥ .
2
21
8
32



6

Hardness of NDP and EDP on Wall Graphs

In this section we extend our results to NDP and EDP on wall graphs, completing the proofs of
Theorem 1.1 and Theorem 1.2. We first prove hardness of NDP-Wall, and show later how to extend
it to EDP-Wall. Let Ĝ = G`,h be a grid of length ` and height h, where ` > 0 is an even integer, and
h > 0. We denote by Ĝ0 the wall corresponding to Ĝ, as defined in Section 2. We prove the following
analogue of Theorem 3.2.
Theorem 6.1 There is a constant c∗ > 0, and there is an efficient randomized algorithm, that,
given a valid instance I = (G̃, U1 , U2 , h, r) of (r,h)-GPwB with |E(G̃)| = M , constructs an instance
Î 0 = (Ĝ0 , M) of NDP-Wall with |V (Ĝ0 )| = O(M 4 log2 M ), such that the following hold:
• If I has a perfect solution (of value β ∗ = β ∗ (I)), then with probability at least 21 over the
β∗
construction of Î 0 , instance Î 0 has a solution P 0 that routes at least c∗ log
demand pairs via
3
M
node-disjoint paths; and
• There is a deterministic efficient algorithm, that, given a solution P ∗ to the NDP-Wall
problem
|P ∗ |
0
instance Î , constructs a solution to the (r,h)-GPwB instance I, of value at least c∗ ·log3 M .
Notice that plugging Theorem 6.1 into the hardness of approximation proof instead of Theorem 3.2, we
extend the hardness result to the NDP problem on wall graphs and complete the proof of Theorem 1.1.
Proof of Theorem 6.1. Let Î = (Ĝ, M) be the instance of NDP-Grid constructed in Theorem 3.2.
In order to obtain an instance Î 0 of NDP-Wall, we replace the grid Ĝ with the corresponding wall Ĝ0
35

as described above; the set of the demand pairs remains unchanged. We now prove the two assertions
about the resulting instance Î 0 , starting from the second one.
Suppose we are given a solution P ∗ to the NDP-Wall problem instance Î 0 . Since Ĝ0 ⊆ Ĝ, and the set of
demand pairs in instances Î and Î 0 is the same, P ∗ is also a feasible solution to the NDP-Grid problem
instance Î, and so we can use the deterministic efficient algorithm
from Theorem 3.2 to construct a
|P ∗ |
solution to the (r,h)-GPwB instance I, of value at least c∗ ·log
.
3
M
It now remains to prove the first assertion. Assume that I has a perfect solution. Let E be the good
β∗
event that the instance Î of NDP-Grid has a solution P that routes at least c∗ log
demand pairs
3
M
via paths that are spaced-out. From Theorem 3.2, event E happens with probability at least 12 . It
β∗
to the
is now enough to show that whenever event E happens, there is a solution of value c∗ log
3
M
corresponding instance Î 0 of NDP-Wall.
Consider the spaced-out set P of paths in Ĝ. Recall that for every pair P, P 0 of paths, d(V (P ), V (P 0 )) ≥
2, and all paths in P are internally disjoint from the boundaries of the grid Ĝ. For each path P ∈ P,
we will slightly modify P to obtain a new path P 0 contained in the wall Ĝ0 , so that the resulting set
P 0 = {P 0 | P ∈ P} of paths is node-disjoint.
For all 1 ≤ i < `, 1 ≤ j ≤ `, let eji denote the ith edge from the top lying in column Wj of the grid Ĝ,
so that eij = (v(i, j), v(i + 1, j)). Let E ∗ = E(Ĝ) \ E(Ĝ0 ) be the set of edges that were deleted from
the grid Ĝ when constructing the wall Ĝ0 . We call the edges of E ∗ bad edges. Notice that only vertical
edges may be bad, and, if eji ∈ E(Wj ) is a bad edge, for 1 < j < `, then ej+1
is a good edge. Consider
i
j
j
some bad edge ei = (v(i, j), v(i + 1, j)), such that 1 < j < `, so ei does not lie on the boundary of Ĝ.
Let Qji be the path (v(i, j), v(i, j + 1), v(i + 1, j + 1), v(i + 1, j)). Clearly, path Qji is contained in the
wall Ĝ0 . For every path P ∈ P, we obtain the new path P 0 by replacing every bad edge eji ∈ P with
the corresponding path Qji . It is easy to verify that P 0 is a path with the same endpoints as P , and
that it is contained in the wall Ĝ0 . Moreover, since the paths in P are spaced-out, the paths in the
resulting set P 0 = {P 0 | P ∈ P} are node-disjoint.

This completes the proof of Theorem 1.1. In order to prove Theorem 1.2, we show an approximationpreserving reduction from NDP-Wall to EDP-Wall.
Claim 6.2 Let I = (G, M) be an instance of NDP-Wall, and let I 0 be the instance of EDP-Wall
consisting of the same graph G and the same set M of demand pairs. Let OPT and OPT0 be the
optimal solution values for I and I 0 , respectively. Then OPT0 ≥ OPT, and there is an efficient
algorithm, that, given any solution P 0 to instance I 0 of EDP-Wall, computes a solution P to instance
I of NDP-Wall of value Ω(|P 0 |).
The following corollary immediately follows from Claim 6.2 and completes the proof of Theorem 1.2.
Corollary 6.3 If there is an α-approximation algorithm for EDP-Wall with running time f (n), for
α > 1 that may be a function of the graph size n, then there is an O(α)-approximation algorithm for
NDP-Wall with running time f (n) + poly(n).
It now remains to prove Claim 6.2.
Proof: The assertion that OPT0 ≥ OPT is immediate, as any set P of node-disjoint paths in the wall
G is also a set of edge-disjoint paths.
Assume now that we are given a set P 0 of edge-disjoint paths in G. We show an efficient algorithm to
compute a subset P ⊆ P 0 of Ω(|P 0 |) paths that are node-disjoint. Since the maximum vertex degree
36

in G is 3, the only way for two paths P, P 0 ∈ P 0 to share a vertex x is when x is an endpoint of at least
one of these two paths. If x is an endpoint of P , and x ∈ V (P 0 ), then we say that P has a conflict
with P 0 .
We construct a directed graph H, whose vertex set is {vP | P ∈ P 0 }, and there is an edge (vP , vP 0 )
iff P has a conflict with P 0 . It is immediate to verify that the maximum out-degree of any vertex in
H is at most 4, as each of the two endpoints of a path P may be shared by at most two additional
paths. Therefore, every sub-graph H 0 ⊆ H of H contains a vertex of total degree at most 8. We
construct a set U of vertices, such that no two vertices of U are connected by an edge, using a
standard greedy algorithm: while H 6= ∅, select a vertex v ∈ H with total degree at most 8 and
add it to U ; remove v and all its neighbors from H. It is easy to verify that at the end of the
algorithm, |U | = Ω(|V (H)|) = Ω(|P 0 |), and no pair of vertices in U is connected by an edge. Let
P = {P | vP ∈ U }. Then the paths in P are node-disjoint, and |P| = Ω(|P 0 |).

Appendix
A

Proof of Theorem 2.4

Suppose G is a Yes-Instance, and let χ be a valid coloring of V (G). Let π1 , . . . , π6 be 6 different
permutations of {r, g, b}. For each 1 ≤ i ≤ 6, permutation πi defines a valid coloring χi of G: for every
vertex v ∈ V (G), if v is assigned a color c ∈ {C} by χ, then χi assigns the color πi (c) to v. Notice that
for each vertex v and for each color c ∈ C, there are exactly two indices i ∈ {1, . . . , 6}, such that χi
assigns the color c to v. Notice also that for each edge (u, v), if c, c0 ∈ C is any pair of distinct colors,
then there is exactly one index i ∈ {1, . . . , 6}, such that u is assigned the color c and v is assigned the
color c0 by χi .
Let B be the set of all vectors of length `, whose entries belong to {1, . . . , 6}, so that |B| = 6` . For each
such vector b ∈ B, we define a perfect global assignment fb of answers to the queries, as follows. Let
Q ∈ QE be a query to the edge-player, and assume that Q = (e1 , . . . , e` ). Fix some index 1 ≤ j ≤ `,
and assume that ej = (vj , uj ). Assume that bj = z, for some 1 ≤ z ≤ 6. We assign to vj the color
χz (vj ), and we assign to uj the color χz (uj ). Since χz is a valid coloring of V (G), the two colors are
distinct. This defines an answer A ∈ AE to the query Q, that determines fb (Q).
Consider now some query Q0 ∈ QV to the vertex-player, and assume that Q0 = (v1 , . . . , v` ). Fix some
index 1 ≤ j ≤ `, and assume that bj = z, for some 1 ≤ z ≤ 6. We assign to vj the color χz (vj ). This
defines an answer A0 ∈ AV to the query Q0 , that determines fb (Q0 ). Notice that for each 1 ≤ j ≤ `,
the answers that we choose for the jth coordinate of each query are consistent with the valid coloring
χbj of G. Therefore, it is immediate to verify that for each b ∈ B, fb is a perfect global assignment.
We now fix some query Q ∈ QE of the edge-prover, and some answer A ∈ AE to it. Assume that
Q = (e1 , . . . , e` ), where for 1 ≤ j ≤ `, ej = (vj , uj ). Let cj , c0j are the assignments to vj and uj given
by the jth coordinate of A, so that cj 6= c0j . Recall that there is exactly one index zj ∈ {1, . . . , 6},
such that χzj assigns the color cj to vj and the color c0j to uj . Let b∗ ∈ B be the vector, where for
1 ≤ j ≤ `, b∗j = zj . Then fb∗ (Q) = A, and for all b 6= b∗ , fb (Q) 6= A.
Finally, fix some query Q0 ∈ QV of the vertex-prover, and some answer A0 ∈ AV to it. Let Q0 =
(v1 , . . . , v` ). Assume that for each 1 ≤ j ≤ `, the jth coordinate of A0 contains the color cj . Recall
that there are exactly two indices z ∈ {1, . . . , 6}, such that χz assigns the color cj to vj . Denote this
set of two indices by Zj ⊆ {1, . . . , 6}. Consider now some vector b ∈ B. If, for all 1 ≤ j ≤ `, bj ∈ Zj ,
then fb (Q0 ) = A0 ; otherwise, fb (Q0 ) 6= A0 . Therefore, the total number of vectors b ∈ B, for which

37

fb (Q0 ) = A0 is exactly 2` .

B

Auxiliary Lemmas

The goal of this section is to prove Lemma 5.2 and Lemma 5.3. We will use the following simple
observation.
Observation B.1 For any two positive integers a and b,

b−1
a+b−1

<

b
a+b .

Recall that we are given a set U of n items, such that P of the items are pink, and the remaining
Y = n − P items are yellow. We consider a random permutation π of these items. Given a set
S ⊆ {1, . . . , n} of δ indices, we let E(S) be the event that for all i ∈ S, the item of π located at the
ith position is yellow.
|S|
Claim B.2 Pr [E(S)] ≤ Yn
.
Proof:
As every subset of δ items of U is equally likely to appear at the indices of S, we get that:
Y
δ

P +Y
δ



Pr [E(S)] =

Y · (Y − 1) · · · (Y − δ + 1)
≤
=
(P + Y ) · (P + Y − 1) · · · (P + Y − δ + 1)



Y
P +Y

δ


=

Y
n

|S|
.

(the last inequality follows from Observation B.1).
We now turn to prove Lemma 5.2.
Lemma B.3 (Restatement of Lemma 5.2.) For any log n ≤ µ ≤ Y , the probability that there is
a sequence of d4nµ/P e consecutive items in π that are all yellow, is at most n/eµ .
m
l
. Consider a set S of δ consecutive indices of {1, . . . , n}. From Claim B.2, the
Proof: Let δ = 4nµ
P
probability that all items located at the indices of S are yellow is at most:


Y
n

δ


=

P
1−
n

d4nµ/P e



P 4nµ/P
≤ 1−
≤ e−µ .
n

Since there are at most n possible choices of a set S of δ consecutive indices, from the Union Bound,
the probability that any such set only contains yellow items is bounded by n/eµ .
Lemma B.4
 (Restatement of Lemma 5.3.) For any log n ≤ µ ≤ P , the probability that there µis
consecutive items in π, such that more than 4µ of the items are pink, is at most n/4 .
a set S of nµ
P
Proof:
 
Let x = nµ
P , and let S be any set of x consecutive indices of {1, . . . , n}. Denote δ = d4µe, and let
0
S ⊆ S be any subset of δ indices from S. From Claim B.2 (by reversing the roles of the pink and
δ
the yellow items),the probability that all items located at the indices of S 0 are pink is at most Pn .
Since there are xδ ways to choose the subset S 0 of S, from the Union Bound, the probability that at
least δ items of S are pink is at most:
38



P
n

δ    δ  
x
P
ex δ
·
≤
·
δ
n
δ
 δ 
e · nµ δ
P
·
≤
n
Pδ

d4µe
e·µ
=
d4µe
 e 4µ
1
≤
< µ.
4
4

Since there are at most n sets S of x consecutive items, taking the Union Bound over all such sets
completes the proof.

C

Proof of Claim 5.13

The goal of this section is to prove Claim 5.13. We show an efficient algorithm to construct a set
P 1 = {P1 , . . . , PM 0 } of spaced-out paths, that originate at the vertices of X on R, and traverse the
boxes K̂j in a snake-like fashion (see Figure 4). We will ensure that for each 1 ≤ i ≤ M 0 and
1 ≤ j ≤ N1 , the intersection of the path Pi with the box K̂j is the ith column of Wj , and that Pi
contains the vertex xi .
Fix some index 1 ≤ j ≤ N1 , and consider the box K̂j . Let Ij0 and Ij00 denote the top and the bottom
boundaries of K̂j , respectively. For each 1 ≤ i ≤ M 0 , let Wji denote the ith column of Wj , and let
x0 (j, i) and x00 (j, i) denote the topmost and the bottommost vertices of Wji , respectively.
For convenience, we also denote I000 = R, and, for each 1 ≤ i ≤ M 0 , x00 (0, i) = xi . The following claim
is central to our proof.
o
n
0
Claim C.1 There is an efficient algorithm to construct, for each 1 ≤ j ≤ N1 , a set Pj = Pj1 , . . . , PjM
of paths, such that:
• For each 1 ≤ j ≤ N1 and 1 ≤ i ≤ M 0 , path Pji connects x00 (j − 1, i) to x0 (j, i);
• The set

SN1

j=1 Pj

• All paths in

SN 1

of paths is spaced-out; and

j=1 Pj

are contained in Gt , and are internally disjoint from R.

S 1
SN1
Notice that by combining the paths in N
j=1 Pj with the set
j=1 Wj of columns of the boxes, we
1
obtain the desired set P of paths, completing the proof of Claim 5.13. In the remainder of this
section we focus on proving Claim C.1.
Recall that each box K̂j is separated by at least 2M columns from every other such box, and from
the left and right boundaries of Ĝ. It is also separated by at least 4M rows from the top boundary of
Ĝ and from the row R. We exploit this spacing in order to construct the paths, by utilizing a special
structure called a snake, that we define next.
Given a set L of consecutive rows of Ĝ and a set W of consecutive columns of Ĝ, we denote by Υ(L, W)
the subgraph of Ĝ spanned by the rows in L and the columns in W; we refer to such a graph as a
39

corridor. Let Υ = Υ(L, W) be any such corridor. Let L0 and L00 be the top and the bottom row of L
respectively, and let W 0 and W 00 be the first and the last column of W respectively. The four paths
Υ∩L0 , Υ∩L00 , Υ∩W 0 and Υ∩W 00 are called the top, bottom, left and right boundaries of Υ respectively,
and their union is called the boundary of Υ. The width of the corridor Υ is w(Υ) = min {|L|, |W|}.
We say that two corridors Υ, Υ0 are internally disjoint, iff every vertex v ∈ Υ ∩ Υ0 belongs to the
boundaries of both corridors. We say that two internally disjoint corridors Υ, Υ0 are neighbors iff
Υ ∩ Υ0 6= ∅. We are now ready to define snakes.
A snake Y of length z is a sequence (Υ1 , Υ2 , . . . , Υz ) of z corridors that are pairwise internally disjoint,
such that for all 1 ≤ z 0 , z 00 ≤ z, Υz 0 is a neighbor of Υz 00 iff |z 0 −z 00 | = 1. The width of the snake is defined
to be the minimum of two quantities: (i) min1≤z 0 <z {|Υz 0 ∩ Υz 0 +1 |}; and (ii) Smin1≤z 0 ≤z {w(Υz 0 )}.
z
Notice that, given a snake Y, there is a unique simple cycle σ(Y) contained in S
z 0 =1 Υz 0 , such that,
if D denotes the disc on the plane whose boundary is σ(Y), then every vertex of zz 0 =1 Υz 0 lies in D,
while every other vertex of Ĝ lies outside D. We S
call σ(Y) the boundary of Y. We say that a vertex u
belongs to a snake Y, and denote u ∈ Y, iff u ∈ zz 0 =1 Υz 0 . We use the following simple claim, whose
proof can be found, e.g. in [CKN17b].
Claim C.2 Let Y = (Υ1 , . . . , Υz ) be a snake of width w, and let A and A0 be two sets of vertices with
|A| = |A0 | ≤ w − 2, such that the vertices of A lie on a single boundary edge of Υ1 , and the vertices of
A0 lie on a single boundary edge of Υz . There is an efficient algorithm, that, given the snake Y, and
the sets A and A0 of vertices as above, computes a set Q of node-disjoint paths contained in Y, that
connect every vertex of A to a distinct vertex of A0 .
Let L, L0 be any pair of rows of G. Let Q be a set of node-disjoint paths connecting some set of vertices
B ⊆ L to B 0 ⊆ L0 . We say that the paths in Q are order-preserving iff the left-to-right ordering of
their endpoints on L is same as that of their endpoints on L0 .
Corollary C.3 Let Y = (Υ1 , . . . , Υz ) be a snake of width w, and let B and B 0 be two sets of r ≤
bw/2c − 1 vertices each, such that the vertices of B lie on the bottom boundary edge of Υ1 , the vertices
of B 0 lie on the top boundary edge of Υz and for every pair v, v 0 ∈ B ∪ B 0 of vertices, dĜ (v, v 0 ) ≥ 2.
There is an efficient algorithm, that, given the snake Y, and the sets B and B 0 of vertices as above,
computes a set Q̂ of spaced-out order-preserving paths contained in Y.
Proof: Let B = {b1 , b2 , . . . , br } and B 0 = {b01 , b02 , . . . , b0r }. Assume that the vertices in both sets are
indexed according to their left-to-right ordering on their corresponding rows of the grid. Since set
B does not contain a pair of neighboring vertices, we can augment it to a larger set A, by adding a
vertex between every consecutive pair of vertices of B. In other words, we obtain A = {a1 , . . . , a2r−1 },
such that for all 1 ≤ i ≤ r, a2i−1 = bi , and the vertices of A are indexed according to their leftto-right
ordering on the bottom boundary of Υ1 . Similarly, we can augment the set B 0 to a set

A0 = a01 , . . . , a02r−1 of vertices, such that for all 1 ≤ i ≤ r, a02i−1 = b0i , and the vertices of A0 are
indexed according to their left-to-right ordering on the top boundary of Υz .
We apply Claim C.2 to the sets A, A0 of vertices, obtaining a set Q of node-disjoint paths, that are
contained in Y, and connect every vertex of A to a distinct vertex of A0 . For all 1 ≤ i ≤ r, let Qi be
the path originating from ai . We claim that Q is an order-preserving set of paths. Indeed, assume for
contradiction that some path Qi ∈ Q connects ai to a0i0 , for i 6= i0 . Notice that the path Qi partitions
the snake Y into two sub-graphs: one containing (i − 1) vertices of A and (i0 − 1) vertices of A0 ; and
the other containing the remaining vertices of A and A0 (excluding the endpoints of Qi ). Since i 6= i0 ,
there must be a path Qi00 ∈ Q intersecting the path Qi , a contradiction to the fact that Q is a set of
node-disjoint paths.

40

Similarly, it is easy to see that for all 1 ≤ i < r, d(Q2i−1 , Q2i+1 ) ≥ 2. This is since the removal of the
path Q2i partitions the snake Y into two disjoint sub-graphs, with path Q2i−1 contained in one and
path Q2i+1 contained in the other.
Our final set of path is Q̂ = {Q2i−1 : 1 ≤ i ≤ r}. From the above discussion, it is a spaced-out set of
paths contained in Y, and for each 1 ≤ i ≤ r, path Q2i−1 ∈ Q̂ connects bi to b0i .
In order to complete the proof, we need the following easy observation.
Observation C.4 There is an efficient algorithm that constructs, for each 1 ≤ j ≤ N1 , a snake Yj of
width at least 2M in Gt , such that all resulting snakes are mutually disjoint, and for each 1 ≤ j ≤ N1 :
00 ;
• the bottom boundary of the first corridor of Yj contains Ij−1

• the top boundary of the last corridor of Yj contains Ij0 ; and
• all snakes are disjoint from R, except for Y1 , that contains I000 ⊆ R as part of is boundary, and
does not contain any other vertices of R.
The construction of the snakes is immediate and exploits the ample space between the boxes K̂j ;
(see Figure 4 for an illustration). From Corollary C.3, for each 1 ≤ j ≤ N1 , we obtain a set Pj of
spaced-out paths contained in Yj , such that for each 1 ≤ i ≤ M 0 , there is a path Pji ∈ Pj connecting
x00 (j − 1, i) to x0 (j, i). For each 1 ≤ i ≤ M 0 , let Pi be the path obtained by concatenating the paths

i
P1i , W1i , P2i , . . . , PNi 1 , WN
. The final set of paths is P 1 = {P1 , . . . , PM 0 }.
1

References
[AAM+ 11] Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein.
Inapproximabilty of densest k-subgraph from average case hardness, 2011.
[ACG+ 10] 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, 2010.
[AGLR94] B. Awerbuch, R. Gawlick, T. Leighton, and Y. Rabani. On-line admission control and
circuit routing for high performance computing and communication. In Proceedings 35th
Annual Symposium on Foundations of Computer Science, pages 412–423, Nov 1994.
[And10]

Matthew Andrews. Approximation algorithms for the edge-disjoint paths problem via
Raecke decompositions. In Proceedings of IEEE FOCS, pages 277–286, 2010.

[AR95]

Yonatan Aumann and Yuval Rabani. Improved bounds for all optical routing. In Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, SODA ’95, pages
567–576, Philadelphia, PA, USA, 1995. Society for Industrial and Applied Mathematics.

[AST94]

Noga Alon, Paul Seymour, and Robin Thomas. Planar separators. SIAM Journal on
Discrete Mathematics, 7(2):184–193, 1994.

[AZ05]

Matthew Andrews and Lisa Zhang. Hardness of the undirected edge-disjoint paths problem. In STOC, pages 276–283. ACM, 2005.

41

[BCC+ 10] Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, and Aravindan Vijayaraghavan. Detecting high log-densities: an O(n 1/4 ) approximation for densest k subgraph. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC
2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 201–210, 2010.
[BFSU98] Andrei Z. Broder, Alan M. Frieze, Stephen Suen, and Eli Upfal. Optimal construction of
edge-disjoint paths in random graphs. SIAM Journal on Computing, 28(2):541–573, 1998.
[BFU92]

Andrei Z. Broder, Alan M. Frieze, and Eli Upfal. Existence and construction of edge
disjoint paths on expander graphs. In Proceedings of the Twenty-fourth Annual ACM
Symposium on Theory of Computing, STOC ’92, pages 140–149, New York, NY, USA,
1992. ACM.

[CC]

Chandra Chekuri and Julia Chuzhoy.
Manuscript.

[CE13]

Chandra Chekuri and Alina Ene. Poly-logarithmic approximation for maximum node
disjoint paths with constant congestion. In Proc. of ACM-SIAM SODA, 2013.

[Chu16]

Julia Chuzhoy. Routing in undirected graphs with constant congestion. SIAM J. Comput.,
45(4):1490–1532, 2016.

[CK15]

Julia Chuzhoy and David H. K. Kim. On approximating node-disjoint paths in grids.
In Naveen Garg, Klaus Jansen, Anup Rao, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA, volume 40 of LIPIcs,
pages 187–211. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2015.

[CKL16]

Julia Chuzhoy, David H. K. Kim, and Shi Li. Improved approximation for node-disjoint
paths in planar graphs. In Proceedings of the 48th Annual ACM SIGACT Symposium on
Theory of Computing, STOC 2016, pages 556–569, New York, NY, USA, 2016. ACM.

Half-integral all-or-nothing flow.

Unpublished

[CKN17a] Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. Improved approximation algorithm for node-disjoint paths in grid graphs with sources on grid boundary. Unpublished
Manuscript, 2017.
[CKN17b] Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat. New hardness results for routing
on disjoint paths. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory
of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 86–99, 2017.
[CKS05]
[CKS06]

Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd. Multicommodity flow, welllinked terminals, and routing problems. In Proc. of ACM STOC, pages 183–192, 2005.
√
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(1):137–146,
2006.

[CKS09]

Chandra Chekuri, Sanjeev Khanna, and F Bruce Shepherd. Edge-disjoint paths in planar
graphs with constant congestion. SIAM Journal on Computing, 39(1):281–301, 2009.

[CL16]

Julia Chuzhoy and Shi Li. A polylogarithmic approximation algorithm for edge-disjoint
paths with congestion 2. J. ACM, 63(5):45:1–45:51, 2016.

[CMS07]

Chandra Chekuri, Marcelo Mydlarz, and F. Bruce Shepherd. Multicommodity demand
flow in a tree and packing integer programs. ACM Trans. Algorithms, 3(3), August 2007.
42

[EIS76]

Shimon Even, Alon Itai, and Adi Shamir. On the complexity of timetable and multicommodity flow problems. SIAM J. Comput., 5(4):691–703, 1976.

[Fei02]

Uriel Feige. Relations between average case complexity and approximation complexity. In
Proceedings of the Thiry-fourth Annual ACM Symposium on Theory of Computing, STOC
’02, pages 534–543, New York, NY, USA, 2002. ACM.

[FHKS03] Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz, and Aravind Srinivasan. Approximating the domatic number. SIAM J. Comput., 32(1):172–195, January 2003.
[FMS16]

Krzysztof Fleszar, Matthias Mnich, and Joachim Spoerhase. New Algorithms for Maximum
Disjoint Paths Based on Tree-Likeness. In Piotr Sankowski and Christos Zaroliagis, editors, 24th Annual European Symposium on Algorithms (ESA 2016), volume 57 of Leibniz
International Proceedings in Informatics (LIPIcs), pages 42:1–42:17, Dagstuhl, Germany,
2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

[Fri00]

Alan M. Frieze. Edge-disjoint paths in expander graphs. In Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’00, pages 717–725, Philadelphia, PA, USA, 2000. Society for Industrial and Applied Mathematics.

[GVY97]

N. Garg, V.V. Vazirani, and M. Yannakakis. Primal-dual approximation algorithms for
integral flow and multicut in trees. Algorithmica, 18(1):3–20, 1997.

[Hol07]

Thomas Holenstein. Parallel repetition: Simplifications and the no-signaling case. In
Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing, STOC
’07, pages 411–419, New York, NY, USA, 2007. ACM.

[Kar75]

R. Karp. On the complexity of combinatorial problems. Networks, 5:45–68, 1975.

[Kho04]

Subhash Khot. Ruling out ptas for graph min-bisection, densest subgraph and bipartite
clique. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer
Science, FOCS ’04, pages 136–145, Washington, DC, USA, 2004. IEEE Computer Society.

[KK13]

Ken-Ichi Kawarabayashi and Yusuke Kobayashi. An O(log n)-approximation algorithm
for the edge-disjoint paths problem in Eulerian planar graphs. ACM Trans. Algorithms,
9(2):16:1–16:13, March 2013.

[Kle05]

Jon Kleinberg. An approximation algorithm for the disjoint paths problem in even-degree
planar graphs. In Proceedings of the 46th Annual IEEE Symposium on Foundations of
Computer Science, FOCS ’05, pages 627–636, Washington, DC, USA, 2005. IEEE Computer Society.

[KR96]

J. Kleinberg and R. Rubinfeld. Short paths in expander graphs. In Proceedings of the
37th Annual Symposium on Foundations of Computer Science, FOCS ’96, pages 86–95,
Washington, DC, USA, 1996. IEEE Computer Society.

[KS04]

Stavros G. Kolliopoulos and Clifford Stein. Approximating disjoint-path problems using
packing integer programs. Mathematical Programming, 99:63–87, 2004.

[KT95]

Jon M. Kleinberg and Éva Tardos. Disjoint paths in densely embedded graphs. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, pages 52–61,
1995.

[KT98]

Jon M. Kleinberg and Éva Tardos. Approximations for the disjoint paths problem in
high-diameter planar networks. J. Comput. Syst. Sci., 57(1):61–73, 1998.
43

[KvL84]

MR Kramer and Jan van Leeuwen. The complexity of wire-routing and finding minimum
area layouts for arbitrary vlsi circuits. Advances in computing research, 2:129–146, 1984.

[LR99]

Tom Leighton and Satish Rao. Multicommodity max-flow min-cut theorems and their use
in designing approximation algorithms. J. ACM, 46(6):787–832, November 1999.

[LT79]

Richard J Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM
Journal on Applied Mathematics, 36(2):177–189, 1979.

[Lyn75]

James F. Lynch. The equivalence of theorem proving and the interconnection problem.
SIGDA Newsl., 5(3):31–36, September 1975.

[Man17]

Pasin Manurangsi. Almost-polynomial ratio eth-hardness of approximating densest ksubgraph. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of
Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 954–961, 2017.

[Räc02]

Harald Räcke. Minimizing congestion in general networks. In Proc. of IEEE FOCS, pages
43–52, 2002.

[Rao08]

Anup Rao. Parallel repetition in projection games and a concentration bound. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC ’08, pages
1–10, New York, NY, USA, 2008. ACM.

[Raz98]

Ran Raz. A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, June 1998.

[RS90]

N. Robertson and P. D. Seymour. Outline of a disjoint paths algorithm. In Paths, Flows
and VLSI-Layout. Springer-Verlag, 1990.

[RS95]

Neil Robertson and Paul D Seymour. Graph minors. XIII. the disjoint paths problem.
Journal of Combinatorial Theory, Series B, 63(1):65–110, 1995.

[RS10]

Prasad Raghavendra and David Steurer. Graph expansion and the unique games conjecture. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC
’10, pages 755–764, New York, NY, USA, 2010. ACM.

[RT87]

Prabhakar Raghavan and Clark D. Thompson. Randomized rounding: a technique for
provably good algorithms and algorithmic proofs. Combinatorica, 7:365–374, December
1987.

[RZ10]

Satish Rao and Shuheng Zhou. Edge disjoint paths in moderately connected graphs. SIAM
J. Comput., 39(5):1856–1887, 2010.

[SCS11]

Loı̈c Seguin-Charbonneau and F. Bruce Shepherd. Maximum edge-disjoint paths in planar
graphs with congestion 2. In Proceedings of the 2011 IEEE 52Nd Annual Symposium on
Foundations of Computer Science, FOCS ’11, pages 200–209, Washington, DC, USA, 2011.
IEEE Computer Society.

[Ung51]

Peter Ungar. A theorem on planar graphs. Journal of the London Mathematical Society,
1(4):256–262, 1951.

44

