Authors Julia Chuzhoy, David Hong Kyun Kim, Rachit Nimavat,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57
www.theoryofcomputing.org
Almost Polynomial Hardness of
Node-Disjoint Paths in Grids
Julia Chuzhoy∗ David Hong Kyun Kim† Rachit Nimavat‡
Received August 2, 2018; Revised April 9, 2020; Published September 22, 2021
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 se-
lected paths are disjoint in their vertices. The best current algorithm for NDP achieves an
√
O( n)-approximation [Kolliopoulos,
√ Stein, Math. Progr. 2004], while the best current neg-
ative result is a factor 2Ω( log n) -hardness of approximation unless NP ⊆ DTIME(nO(log n) )
[Chuzhoy, Kim, Nimavat, STOC’17], even if the underlying graph is a subgraph of a grid
graph; 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 Õ(n1/4 ), and the best current lower bound
of APX-hardness [Chuzhoy, Kim, APPROX’15] only ruling out a (1+δ )-approximation
algorithm for some fixed δ > 0, assuming that P 6= NP. In this paper we come close to
An extended abstract of this paper appeared in the Proceedings of the 50th Annual ACM Symposium on Theory of
Computing (STOC’18) [20].
∗ Supported in part by NSF grants CCF-1318242 and CCF-1616584.
† Supported in part by NSF grant CCF-1318242 and CCF-1616584.
‡ Supported in part by NSF grant CCF-1318242 and CCF-1616584.
ACM Classification: F.2.2
AMS Classification: 68Q17, 68Q25, 68W25
Key words and phrases: disjoint paths, graph routing, hardness of approximation
© 2021 Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2021.v017a006
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
resolving the approximability of NDP in general, and of NDP in grids in particular. Our
1−ε
main result is that NDP is 2Ω(log n) -hard to approximate for any constant ε, assuming that
2
NP * DTIME(npoly log n ), and that it is nΩ(1/(log log n) ) -hard to approximate, assuming that for
δ
some constant δ > 0, NP 6⊆ DTIME(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.
Contents
1 Introduction 3
2 Preliminaries 7
3 The (r, h)-Graph Partitioning problem 13
4 Tools for the hardness proof 15
4.1 From 3COL(5) to (r,h)-GPwB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.2 From (r,h)-GPwB to NDP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.3 Combining the tools for the Y ES -I NSTANCE . . . . . . . . . . . . . . . . . . . . . . . . 18
5 The hardness proof 19
5.1 Proof of Theorem 5.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
6 Reduction from (r,h)-GPwB to NDP-Grid 28
6.1 Proof intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.2 The construction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
6.3 From partitioning to routing: proof of Theorem 6.5 . . . . . . . . . . . . . . . . . . . . 34
6.3.1 Proof of Lemma 6.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
6.3.2 Proof of Lemma 6.9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
6.4 From routing to partitioning: proof of Theorem 6.6 . . . . . . . . . . . . . . . . . . . . 40
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 2
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
7 Hardness of NDP and EDP on wall graphs 46
A Proof of Theorem 2.6 48
B Proof of Observation 6.4 49
C Proof of Claim 6.13 49
D Acknowledgment 52
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: 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 [49, 50] 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 input, the problem becomes NP-hard [30, 23], and it remains NP-hard even for planar
graphs [41], and for grid graphs [38]. The best current upper bound on the approximability of NDP is
√
O( n), obtained by a simple greedy algorithm [37]. Until recently, the best known lower bound was an
Ω(log1/2−ε n)-hardness of approximation for any constant ε, unless NP ⊆ ZPTIME(npoly log n ) [5, 4]. For
the special cases of NDP-Planar and NDP-Grid [17], the best known lower bound was APX-hardness, so
√ for some fixed δ > 0, unless P = NP. In a recent
that they do not have a (1+δ )-approximation algorithm,
paper [19], 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 subgraphs 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 [37] was recently slightly improved to an Õ(n9/19 )-approximation [18].
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 well-structured, one
would expect that good approximation algorithms can be designed for them, or that, at the very least,
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 3
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
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 [37] was only recently improved to
a Õ(n1/4 )-approximation for NDP-Grid [17], while on
√ the negative side only APX-hardness is known. In
a very recent paper [21], the authors designed a 2 log n·log log n) -approximation algorithm for a special
O(
case of NDP-Grid, where √ the source vertices appear on the grid boundary. This result can be seen as
complementing the 2 log n) -hardness of approximation of NDP on subgraphs of grids with all sources
Ω(
lying on the grid boundary [19].1 Furthermore, this result can be seen as suggesting that subpolynomial
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 approximability
1−ε
status of NDP-Grid, and of NDP in general, by showing that NDP-Grid is 2Ω(log n) -hard to approximate
2
for any constant ε, unless2 NP ⊆ DTIME(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⊆ DTIME(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 algorithm for
NDP-Grid with all sources lying on the grid boundary [21].
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 [13], and the recent 2Ω( log n) -hardness of approximation of [19], 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 constant-factor approximation for this special case [6, 36, 35]. 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 wall
graphs is similar to that of NDP on grid graphs, with the best current upper 1/4 ), and the best
√ bound of Õ(n
lower bound of APX-hardness [17]. The results of [19] extend to a 2Ω( log n) -hardness of approximation
for EDP on subgraphs 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.
1 Note that the results are not strictly complementary: the algorithm only works for grid graphs, while the hardness result is
only valid for subgraphs of grids.
2 The original version of this paper contained a randomized reduction, with a somewhat stronger complexity assumptions that
δ
NP 6⊆ RTIME(npoly log n ) and NP 6⊆ RTIME(2n ), respectively. The derandomization strategy that we have used was proposed
to us by a reviewer.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 4
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
Figure 1: A wall graph.
Other related work. Several other special cases of EDP are known to have reasonably good approxi-
mation algorithms. For example, for the special case of Eulerian planar graphs, Kleinberg [33] showed
an O(log2 n)-approximation algorithm, while Kawarabayashi and Kobayashi [31] 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 [39, 10, 9, 34, 27], and constant-factor
approximation algorithms are known for trees [28, 15], and grids and grid-like graphs [6, 7, 36, 35]. Rao
and Zhou [47] 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. [26] designed an O( r · log(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) prob-
lem, 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
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 [44], that introduced the randomized
LP-rounding technique, obtained a constant-factor approximation for NDPwC and EDPwC, for a con-
gestion value c = Θ(log n/ log log n). A long sequence of work [12, 43, 3, 47, 16, 22, 11] has led to an
O(poly log k)-approximation for EDPwC with congestion bound c = 2, and for NDPwC with constant
congestion. These results are 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 to within
1−ε
a factor Ω((log n) c+1 ), unless NP ⊆ ZPTIME(npoly log n ) [4]. When the input graph is planar, Seguin-
Charbonneau and Shepherd [51], improving on the result of Chekuri, Khanna and Shepherd [14], 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 polynomial-time algorithm
2
for NDP, assuming that NP * DTIME(npoly log n ). Moreover, there is no nO(1/(log log n) ) -approximation
δ
polynomial-time algorithm for NDP, assuming that for some constant δ > 0, NP * DTIME(2n ). These
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 5
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
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 polynomial-time algorithm
2
for EDP, assuming that NP * DTIME(npoly log n ). Moreover, there is no nO(1/(log log n) ) -approximation
δ
polynomial-time algorithm for EDP, assuming that for some constant δ > 0, NP * DTIME(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 Parti-
tioning, 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 for 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
to approximate 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 ε [8]. Even though the problem appears to be very hard to approx-
imate, its hardness-of-approximation proof has been elusive until recently: only constant-factor hardness
2/3
results were known for DkS under various worst-case complexity assumptions, and 2Ω(log n) -hardness
under average-case assumptions [24, 1, 32, 45]. In a recent breakthrough, Manurangsi [42] has shown
c
that for some constant c, DkS is hard to approximate to 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 [42] to this problem, or to prove its hardness of approximation via other techniques.
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 I j of instances of NDP-Grid, and
apply the algorithm A to each of them. If the 3COL(5) instance is a Y ES -I NSTANCE, then we are
guaranteed that each resulting instance of NDP-Grid has a large solution, and so all solutions returned by
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 6
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
A are large. If the 3COL(5) instance is a N O -I NSTANCE, 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 I j+1 of instances of NDP-Grid.
While in the Y ES -I NSTANCE case we will continue to obtain large solutions to all NDP-Grid instances
that we construct, we can show that in the N O -I NSTANCE 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 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 [19]. The proof in [19] proceeded by performing a reduction from 3SAT(5). Initially, a simple reduction
from 3SAT(5) to the NDP problem on a subgraph 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 Y ES -I NSTANCE and N O -I NSTANCE solutions.
Organization. We start with Preliminaries in Section 2, and introduce the new graph partitioning
problems in Section 3. We introduce two main tools that we use in the hardness-of-approximation proof
in Section 4. The tools are a reduction from 3COL to the graph partitioning problem, and a reduction
from the graph partitioning problem to NDP-Grid. The hardness-of-approximation proof for NDP-Grid
appears in Section 5, with the details of the reduction from the graph partitioning problem to NDP-Grid
deferred to Section 6. Finally, we extend our hardness results to NDP-Wall and EDP-Wall in Section 7.
2 Preliminaries
All graphs in this paper are simple. 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 if
every vertex in P ∩U is an endpoint of P. Similarly, we say that P is internally disjoint from a subgraph
G0 of G if 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 M0 . Given a graph G and a vertex v ∈ V (G), we denote by dG (v) the degree of v in G. All
logarithms in this paper are to the base of 2.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 7
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
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 = {(v(i, j), v(i, j + 1)) | 1 ≤ i ≤ h, 1 ≤ j < `} of horizontal edges and the set
E V = {(v(i, j), v(i + 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 W j 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 if 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 W0 of consecutive columns of G, the sub-
grid of G spanned by the rows in R0 and the columns in W0 is the subgraph of G induced by the set
{v | row(v) ∈ R0 , col(v) ∈ W0 } of its vertices.
Given two vertices u = v(i, j) and u0 = v(i0 , j0 ) 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 W j of the grid, let e1j , . . . , eh−1
j
be the edges of W j indexed in their
∗ j
top-to-bottom order. Let E (G) ⊆ E(G) contain all edges ez , where z 6= j mod 2, and let Ĝ be the graph
obtained from G \ E ∗ (G), by deleting all degree-1 vertices from it. Graph Ĝ is called a wall of length `/2
and height h (see Figure 1). Consider the subgraph of Ĝ induced by all horizontal edges of the grid G
that belong to Ĝ. This graph is a collection of h node-disjoint paths, that we refer to as the rows of Ĝ, and
denote them by R1 , . . . , Rh in this top-to-bottom order; notice that R j is also the jth row of the grid G for
all j. Graph Ĝ 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 Ĝ,
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 Ĝ, respectively, and their union is the boundary of Ĝ.
Semiregular bipartite graphs. We will use the following notion of semiregular bipartite graphs.
Definition 2.1. Let G = (A, B, E) be a bipartite graph. We say that G is (d, d 0 )-semiregular, for integers
d, d 0 > 0 if the following hold:
• For every vertex v ∈ A, d ≤ dG (v) < 2d;
• For every vertex u ∈ B, dG (u) < 2d 0 ; and
• |E| ≥ d 0 |B|/(4 log |B|) if |B| > 1, and |E| = d 0 otherwise.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 8
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
We say that G is semiregular if it is (d, d 0 )-semiregular for any integers d, d 0 > 0.
Claim 2.2. There is a polynomial-time algorithm, that, given any bipartite graph G = (A, B, E) with
|A|, |B| > 1, computes a semiregular subgraph G0 = (A0 , B0 , E 0 ) of G, with A0 ⊆ A, B0 ⊆ B, and |E 0 | ≥
Ω(|E|/(log |A| log |B|)).
(We note that, if |A| = 1 or |B| = 1, then the graph is semiregular by definition.)
Proof. We transform the graph G into a semiregular graph G0 in two steps. In the first step, we regularize
the degrees of the vertices of B. We partition the vertices in B into r = dlog |A|e + 1 groups Y1 , . . . ,Yr , as
follows: group Yi contains all vertices u ∈ B with 2i ≤ dG (u) < 2i+1 . If a vertex u ∈ B belongs to group
Yi , then we say that all edges that are incident to u also belong to group Yi . Clearly, there is some index
1 ≤ i ≤ r, such that at least |E|/r = Ω(|E|/ log |A|) edges of E belong to group Yi . We let d 0 = 2i , and we
define a new bipartite graph Ĝ. The set of vertices consists of the set A, and of a set B0 ⊆ B, containing all
vertices that belong to group Yi . The set of edges, that we denote by Ê, contains all edges of E that are
incident to the vertices of B0 . Notice that |Ê| ≥ d 0 |B0 |.
In the second step, we similarly regularize the degrees of the vertices in A. We partition the vertices
of A into r0 = dlog |B0 |e + 1 groups X1 , . . . , Xr0 , as follows: group Xi contains all vertices v ∈ A with
2 j ≤ dĜ (v) < 2 j+1 . If a vertex v ∈ A belongs to group X j , then we say that all edges that are incident to v
in Ĝ also belong to group X j . Clearly, there is some index 1 ≤ j ≤ r0 , such that at least
d 0 |B0 | d 0 B0
|Ê| |E|
≥ ≥ ≥Ω
r0 dlog |B0 |e + 1 4 log |B0 | log |A| log |B|
edges of Ê belong to group X j . We set d = 2 j . We now define the final bipartite graph G0 = (A0 , B0 , E 0 ).
The set B0 of vertices remains the same as before. The set A0 of vertices contains every vertex of A that
belongs to class X j . The set E 0 of edges contains every edge of Ê that is incident to a vertex in A0 . It is now
immediate to verify that for every vertex v ∈ A0 , d ≤ dG0 (v) < 2d, and for every vertex u ∈ B0 , dG0 (u) <
2d 0 . From the above discussion, |E 0 | ≥ Ω(|E|/ log |A| log |B|). Moreover, |E 0 | ≥ d 0 |B0 |/(4 log |B0 |) as
required.
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 χif χ(u) 6= χ(v). We say that the
coloring χ is valid if it satisfies every edge. We say that G is a Y ES -I NSTANCE if there is a valid coloring
χ : V → C. We say that it is a N O -I NSTANCE with respect to some given parameter ε if 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. [25]:
Theorem 2.3 (Proposition 15 in [25]). There is some constant ε, such that distinguishing between the
Y ES -I NSTANCES and the N O -I NSTANCES (with respect to ε) of 3COL(5) is NP-hard.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 9
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
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 edge e to the
edge-prover and vertex 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 Y ES -I NSTANCE, 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 N O -I NSTANCE, 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 vertex-prover. 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 edge-prover. 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 1/2, and so overall
the verifier rejects with probability at least ε/2. Therefore, if G is a Y ES -I NSTANCE, then the value of the
corresponding game is 1, and if it is a N O -I NSTANCE, 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 e j 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 e j 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, if it causes the verifier to accept. We let G` denote this 2-prover
protocol with ` repetitions.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 10
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
Theorem 2.4 (Parallel Repetition, [48, 29, 46]). 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 from ` > 0 parallel
0
repetitions of G̃, is at most xγ ` .
Corollary 2.5. There is some constant 0 < γ < 1, such that, if G is a Y ES -I NSTANCE, then G` has value
1, and if G is a N O -I NSTANCE, 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, and |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 if 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 if 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 Y ES -I NSTANCE case, there are many perfect global assignments, that neatly
partition all answers to the edge-queries.
Theorem 2.6. Assume that G is a Y ES -I NSTANCE. 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 .
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 11
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
Constraint graph H. 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)` .
Assignment graphs L(H 0 ). 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 convenient for now to think that H 0 = H, but later we will use smaller subgraphs 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 Û E the resulting set of vertices:
Û 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 Û V the resulting set of
vertices: n o
Û 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 Û E ∪ Û 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
n o
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 Ê 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 Û E of vertices into groups S(Q)—one group for each
query Q ∈ QE with v(Q) ∈ H 0 . We denotethis partition by U1 . Similarly, we have defined a partition of
Û 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` .
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 12
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
Finally, we need to define bundles of edges in the graph L(H 0 ). For every vertex v ∈ Û E ∪ Û 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 ∈ Û E ∪ Û 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 some query 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 edges of Ê, as each such edge
S
belongs to two bundles. However, each of v∈Û E B(v) and v∈Û V B(v) does define a partition of Ê. It is
S S
easy to verify that every bundle that we have defined contains exactly 2` edges. We use this fact later.
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 NDP-Grid.
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, 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 constraint graph H, and the assignment
graph L(H), as described in Section 2. We can then view L(H) as an instance of (r,h)-GP, with r = 6` and
h = |R|. Assume that G is a Y ES -I NSTANCE. Then we can use the perfect global assignments f1 , . . . , fr
of answers to the queries, given by Theorem 2.6, in order to partition the vertices of L(H) into r = 6`
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 13
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
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 v j (Q0 , A0 ), where A0 = fi (Q0 ), and the indices j are chosen so that every
vertex v j (Q0 , A0 ) participates in exactly one cluster Wi . From the construction of the assignment graph
L(H) and the properties of the assignments fi guaranteed by Theorem 2.6, 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 N O -I NSTANCE, 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 solutions.3 Moreover,
unlike in the Y ES -I NSTANCE 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 problem is to impose additional restrictions on the feasible solutions
to the (r,h)-GP problem, which are consistent with our Y ES -I NSTANCE 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 Y ES -I NSTANCE, 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 group 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 , such that some edge of E
connects v to a vertex of U, 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 partitioned,
and we denote by β (v) = |B(v)| the number of such bundles. We also denote by B = v∈V1 ∪V2 B(v)—the
S
set of all bundles. Note that as before, B is not a partition of E, 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
S S
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 ≤ r,
for every bundle B ∈ B, Ei contains at most one edge e ∈ B. As before, the goal is to maximize ∑i |Ei |.
3 We note that a similar problem arises if one attempts to design naive hardness-of-approximation proofs for DkS.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 14
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
Valid instances, regular instances, and perfect solutions. Given an instance
I = (G̃ = (V1 ,V2 , E), U1 , U2 , h, r)
of (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 3.1. We say that instance I of (r,h)-GPwB is valid if 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 Y ES -I NSTANCE are always perfect, as we
show later.
Definition 3.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.
Lastly, we say that an instance I = (G̃ = (V1 ,V2 , E), U1 , U2 , h, r) of the (r,h)-GPwB problem is (d1 , d2 , b)-
regular if the graph G̃ is (d1 , d2 )-semiregular, and for every vertex v ∈ V1 ∪V2 , every bundle B ∈ B(v)
has cardinality exactly b.
4 Tools for the hardness proof
In this section we provide two basic tools that will be used in the hardness-of-approximation proof: a
reduction from the 3COL(5) problem to the (r,h)-GPwB problem, and a reduction from the (r,h)-GPwB
problem to the NDP-Grid problem. We also establish some properties of these reductions that will be
used later.
4.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 connected
subgraph H 0 ⊆ H. We define an instance I(H 0 ) of (r,h)-GPwB, as follows. First, we use Claim 2.2
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 15
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
in order to compute a semiregular subgraph H 00 ⊆ H 0 , with |E(H 00 )| ≥ Ω(|E(H 0 )|/ log2 |E(H 0 |). In our
reduction, we will work with the graph H 00 instead of the graph H 0 from now on. We now define the
instance I(H 0 ) of (r,h)-GPwB.
• The underlying graph is L(H 00 ) = (Û E , Û V , Ê);
• the parameters are r = 6` and h = |E(H 00 )|;
• the partition U1 of Û E is the same as before: the vertices of Û E are partitioned into groups S(Q)—
one group for each query Q ∈ QE with v(Q) ∈ V (H 00 ). Similarly, the partition U2 of Û V into groups
is also defined exactly as before, and contains, for each query Q0 ∈ QV with v(Q0 ) ∈ V (H 00 ), a group
S(Q0 ). (Recall that for all Q ∈ QE ∪ QV with v(Q) ∈ H 0 , |S(Q)| = 6` .)
Claim 4.1. Let G be an instance of the 3COL(5) problem, ` > 0 an integral parallel repetition parameter,
and H 0 ⊆ H a connected 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, it is a (d 0 , d 00 , b)-regular instance for some
d 0 , d 00 > 0 and b = 2` , and moreover, if G is a Y ES -I NSTANCE, 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 00 . The total number of bundles incident to the vertices of S(Q)
is then the degree of v(Q) in H 00 times |AE |. Therefore, β ∗ (I) = ∑v(Q,A)∈Û E |β (v)| = |E(H 00 )| · |AE | =
h · r. It is now immediate to verify that h = β ∗ (I)/r. Similarly, for a vertex v = v j (Q0 , A0 ) ∈ U V , the
number of bundles incident to v is exactly the degree of v(Q0 ) in H 00 . Since h = |E(H 00 )|, we get that
h ≥ maxv∈V1 ∪V2 {β (v)}, and so I(H 0 ) is a valid instance.
Next, we show that I(H 0 ) is a (d 0 , d 00 , b)-regular instance, for some d 0 , d 00 > 0 and b = 2` . Denote
I(H 0 ) = (G̃ = (V1 ,V2 , E), U1 , U2 , h, r). Recall that we have defined a graph H 00 ⊆ H 0 , that is (d1 , d2 )-
semiregular, for some d1 , d2 > 0. Recall also that, from the discussion at the end of Section 2, for every
vertex v ∈ V1 ∪V2 , every bundle B ∈ B(v) contains exactly 2` edges. Moreover, if v ∈ S(Q) for any query
Q, then the number of its bundles β (v) is exactly the degree of the vertex v(Q) in graph H 00 . Therefore,
dG̃ (v) = 2` · dH 00 (v(Q)). It follows that for every vertex v ∈ V1 , d1 · 2` ≤ dG̃ (v) < 2d1 · 2` , and for every
vertex v0 ∈ V2 , dG̃ (v0 ) < 2d2 · 2` . Moreover, |E(G̃)| = 12` · |E(H 00 )|.
Recall that V (H 0 ) = U E ∪U V , where the vertices of U E represent the edge-queries, and the vertices of
U V represent the vertex-queries. Since, from the definition of semiregular graphs, we are guaranteed that
|E(H 00 )| ≥ d2 |U V ∩V (H 00 )|/(4 log |U V ∩V (H 00 )|), and |V2 | = 6` · |U V ∩V (H 00 )|, we get that:
12` · d2 |U V ∩V (H 00 )|
|E(G̃)| = 12` · |E(H 00 )| ≥
4 log |U V ∩V (H 00 )|
(d2 · 2` ) · |V2 | (d2 · 2` ) · |V2 |
≥ ≥ .
4 log |U V ∩V (H 00 )| 4 log |V2 |
We conclude that instance I(H 0 ) is (d 0 , d 00 , b)-regular, for d 0 = 2` · d1 , d 00 = 2` · d2 , and b = 2` .
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 16
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
Assume now that G is a Y ES -I NSTANCE. We define a perfect solution ((W1 , . . . ,Wr ), (E1 , . . . , Er )) to
instance I(H 0 ) of the (r,h)-GPwB problem. Let { f1 , f2 , . . . , f6` } be the collection of perfect global assign-
U | Q ∈ QE , v(Q) ∈ H 00
ments of answers to the queries, given by Theorem 2.6. Recall that 1 = S(Q)
and U2 = S(Q0 ) | Q0 ∈ QV , v(Q0 ) ∈ H 00 , 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 with
v(Q) ∈ V (H 00 ), if A = fi (Q), then we add the vertex v(Q, A) to Wi . For each query Q0 ∈ QV to the
vertex-prover with v(Q0 ) ∈ V (H 00 ), if A0 = fi (Q0 ), then we select some index 1 ≤ j ≤ 2` , and add the
vertex v j (Q0 , A0 ) to Wi . The indices j are chosen so that every vertex v j (Q0 , A0 ) participates in at most one
cluster Wi . From the construction of the graph L(H 00 ) and the properties of the assignments fi guaranteed
by Theorem 2.6, it is easy to verify that W1 , . . . ,Wr partition the vertices of L(H 00 ), 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 00 , set Wi contains a pair of vertices v(Q, A), v j (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 00 ) belongs to Ei . Therefore, |Ei | = |E(H 00 )| = h.
Claim 4.1 shows that, if an instance G of the 3COL(5) problem is a Y ES -I NSTANCE, then the correspond-
ing instance I(H) of (r,h)-GPwB has a solution of a high value (a perfect solution). Ideally, we would
like to show that, if G is a N O -I NSTANCE, then any solution to the corresponding (r,h)-GPwB instance
has a low value. Unfortunately, we cannot do this directly, and this is the reason that our hardness-of-
approximation proof, provided in Section 5, employs a Cook reduction and not a Karp reduction. As
we will show in Section 5, if instance G of 3COL(5) is a N O -I NSTANCE, but the corresponding instance
of (r,h)-GPwB has a high solution value, then we can exploit the solution to the (r,h)-GPwB problem
instance in order to compute a partition of the constraint graph H into smaller subgraphs, and then employ
the same reduction on each one of the resulting subgraphs; see Section 5 for more details.
4.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 4.2. Let P be a set of paths in a grid Ĝ. We say that P is a spaced-out set if for each pair
P, P0 ∈ P of paths, d(V (P),V (P0 )) ≥ 2, and all paths in P are internally disjoint from the boundaries of
the grid Ĝ.
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.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 17
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
Theorem 4.3. There is a constant c∗ > 0, and there is an algorithm, that, given a valid and a (d, d 0 , b)-
regular instance I = (G̃, U1 , U2 , h, r) of (r,h)-GPwB, for some d, d 0 , b > 0, with |V (G̃)| = N and |E(G̃)| =
M, in time poly(NM) constructs an instance Î = (Ĝ, M) of NDP-Grid with |V (Ĝ)| = O(M 4 log2 M), such
that the following hold:
• if I has a perfect solution (of value β ∗ = β ∗ (I)), then instance Î has a solution P that routes at
β∗
least c∗ log 2
M
demand pairs, such that the paths in P are spaced-out; and
• there is an algorithm with running time poly(NM), that, given a solution P∗ to the NDP-Grid
|P∗ |
problem instance Î, constructs a solution to the (r,h)-GPwB instance I, of value at least c∗ ·log 3
M
.
We note that the theorem is slightly stronger than what is needed in order to prove hardness of approxi-
mation 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 Î 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 6.
4.3 Combining the tools for the Y ES -I NSTANCE
Assume now that we are given an instance G of 3COL(5), an integral parallel repetitions parameter ` > 0,
and a connected subgraph H 0 ⊆ H of the corresponding constraint graph. Recall that we have constructed
a corresponding instance I(H 0 ) of (r,h)-GPwB that is valid and (d, d 0 , b)-regular for some d, d 0 , b > 0.
We can then use Theorem 4.3 to construct an instance of NDP-Grid, that we denote by Î(H 0 ). Note that
|E(L(H 00 ))| ≤ 2O(`) · |E(H)| ≤ nO(`) . Let ĉ be a constant, such that |E(L(H 00 ))| ≤ nĉ` for any connected
subgraph H 0 ⊆ H; we can assume w.l.o.g. that ĉ > 1. We can also assume w.l.o.g. that c∗ ≥ 1, where c∗ is
the constant from Theorem 4.3, and we assume that the algorithm from Claim 2.2 returns a subgraph
G0 = (A0 , B0 , E 0 ) of G with |E 0 | ≥ |E(G)|/(c∗ log2 |E(G)|), if G is a connected graph. Lastly, we denote
cYI = (ĉ · c∗ )4 . We obtain the following immediate corollary of Theorem 4.3:
Corollary 4.4. Suppose we are given 3COL(5) instance G that is a Y ES -I NSTANCE, an integral parallel
repetition parameter ` > 0, and a connected subgraph H 0 ⊆ H of the corresponding constraint graph.
Then instance Î(H 0 ) of NDP-Grid has a solution of value at least
|E(H 0 )| · 6`
,
cYI `4 log4 n
where n = |V (G)|.
Proof. From Claim 4.1, instance I(H 0 ) = (L(H 00 ), U1 , U2 , r, h) of (r,h)-GPwB is a valid instance, it
is a (d 0 , d 00 , b)-regular instance for some d 0 , d 00 , b > 0, and it has a perfect solution, whose value is
β ∗ = β ∗ (I(H 00 )) = h · r = |E(H 00 )| · 6` . Recall that H 00 is a semiregularized graph, that was obtained from
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 18
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
H 0 by applying Claim 2.2 to it, so |E(H 00 )| ≥ |E(H 0 )|/(c∗ log2 |E(H 0 )|). From Theorem 4.3, instance
Î(H 0 ) of NDP-Grid has a solution of value at least
|E(H 00 )| · 6` |E(H 0 )| · 6`
≥ ,
c∗ log |E(H 00 )| (c∗ )2 log4 M
2
where M = |E(L(H 00 ))|. Since log M ≤ ĉ` log n, the corollary follows.
As already mentioned before, if G is a N O -I NSTANCE, it is still possible that the corresponding instance
of (r,h)-GPwB, and hence the resulting instance of NDP-Grid, will have a high solution value. We get
around this problem by employing a Cook reduction, as shown in Section 5.
5 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.5). We will set the value of the parallel repetition 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
corresponding graph H (the constraint graph), together with the assignment 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 Î(H) of NDP-Grid.
Note that, if G is a Y ES -I NSTANCE, then from Corollary 4.4, there is a solution to Î(H) of value at
`
least c |R|·6
` log4 n
4 . Assume now that G is a N O -I NSTANCE. If we could show that any solution to the
YI
`
corresponding (r,h)-GPwB instance I(H) has value less than c2 ·α|R|·6
∗ `7 log7 n , we would be done. Indeed,
YI
in such a case, from Theorem 4.3, every solution to the NDP-Grid instance Î(H) routes fewer than
|R|·6`
c α ∗ `4 log4 n
demand pairs. If we assume for contradiction that an α ∗ -approximation algorithm exists for
YI
NDP-Grid, then, if G is a Y ES -I NSTANCE, the algorithm would have to return a solution to Î(H) routing
`
at least c α|R|·6
∗ `4 log4 n demand pairs, while, if G is a N O -I NSTANCE , no such solution would exist. Therefore,
YI
we could use the α ∗ -approximation algorithm for NDP-Grid to distinguish between the Y ES -I NSTANCES
and the N O -I NSTANCES of 3COL(5).
Unfortunately, we are unable to prove this directly. For simplicity, assume that H is a semiregular graph.
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 N O -I NSTANCE. But a cheating solution may place many vertices from the same set
S(Q) into some cluster W j . 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 W j . The main idea in our
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 19
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
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 subgraphs of
H decrease very fast. The main tool that allows us to execute this plan is the following theorem.
Theorem 5.1. Suppose we are given an instance G of the 3COL(5) problem with |V (G)| = n, and
an integral parallel repetition parameter ` > log2 n, together with some connected subgraph H 0 ⊆ H
of the corresponding constraint graph H. 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 `
2 ∗ 7 7 O(`)
)| · 6 /α, where α =
cYI · α · ` log n. Then there is an algorithm, whose running time is O n , that returns one of the
following:
• Either a strategy for the two provers that satisfies more than a 2−γ`/2 -fraction of the constraints
R ∈ R with e(R) ∈ E(H 0 ); or
• a collection H of disjoint connected subgraphs of H 0 , such that for each H̃ ∈ H, |E(H̃)| ≤
|E(H 0 )|/2γ`/16 , and ∑H̃∈H |E(H̃)| ≥ c0 |E(H 0 )|/(`2 α 2 ), for some universal constant 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
Y ES -I NSTANCES and the N O -I NSTANCES of 3COL(5) with |V (G)| = n. Suppose we are given an
instance G of 3COL(5).
For an integral parallel repetition parameter ` > log2 n, let H be the constraint graph corresponding to
G and `. We next show an algorithm, that uses A as a subroutine, in order to determine whether G is a
Y ES -I NSTANCE or a N O -I NSTANCE. The running time of the algorithm is nO(`) .
Throughout the algorithm, we maintain a collection H of disjoint connected subgraphs 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 clusters. Consider now some inactive cluster H
0 ∈ H . This cluster defines
2
a 2-prover game G(H ), where the queries to the two provers are Q ∈ QE | v(QE ) ∈ V (H 0 ) , and
0 E
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 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, the clusters in H are the connected components of H, and every cluster is active. The
algorithm is executed while H1 6= 0,/ and its execution is partitioned into phases. In every phase, we
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 20
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
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).
I TERATION FOR P ROCESSING A C LUSTER H 0 ∈ H1
1. Construct an instance I(H 0 ) of (r,h)-GPwB.
2. Use Theorem 4.3 to construct an instance Î(H 0 ) of the NDP-Grid problem.
3. Run the α ∗ -approximation algorithm A on this instance. If the resulting solution routes
0 )|6`
fewer than c |E(H
α ∗ `4 log4 n
demand pairs, halt and return “G is a N O -I NSTANCE.”
YI
0 `
4. Otherwise, consider the returned solution routing at least c |E(H )|6
α ∗ `4 log4 n
demand pairs.
YI
Denote |E(L(H 00 ))| = M, and recall that M ≤ nĉ` . Use Theorem 4.3 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 α ∗ `4 log4 n)(c∗ log3 M) cYI c∗ ĉ3 α ∗ `7 log7 n c2YI α ∗ `7 log7 n α
5. Apply the algorithm from Theorem 5.1 to this solution.
(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 subgraphs of H 0 returned by the algorithm.
Remove H 0 from H1 and add all graphs of H̃ to H1 .
Figure 2: Description of an iteration
If the algorithm terminates with H containing only inactive clusters, then we return “G is a Y ES -
I NSTANCE.”
Correctness. We establish the correctness of the algorithm in the following two lemmas.
Lemma 5.2. If G is a Y ES -I NSTANCE, then the algorithm always returns “G is a Y ES -I NSTANCE.”
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 N O -I NSTANCE in Step (3).
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 21
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
Instance Use Theorem 4.2 to
construct instance Î(H’) of Run algorithm 𝒜
𝐻" ∈ ℋ% 𝐼 𝐻 " of
NDP-grid on Î(H’)
(r,h)-GPwB
solution has
small value
solution has large value
𝐺 is a
Use Theorem 4.2 to find a No-Instance
large solution to I(H " );
apply Theorem 5.1 to I(H’)
Replace 𝐻′ with Classify 𝐻′ as
new clusters in ℋ% good partition good strategy for provers inactive
Figure 3: Flowchart for the execution of an iteration
From Corollary 4.4, an instance Î(H 0 ) of NDP-Grid is guaranteed to have a solution of value at least
|E(H 0 )| · 6`
ψ := ,
cYI `4 log4 n
and our α ∗ -approximation algorithm to NDP-Grid must then return a solution of value at least ψ/α ∗ .
Therefore, our algorithm will never return “G is a N O -I NSTANCE.”
Lemma 5.3. If G is a N O -I NSTANCE, then the algorithm always returns “G is a N O -I NSTANCE.”
Proof. From Corollary 2.5, it is enough to show that, whenever the algorithm classifies G as a Y ES -
I NSTANCE, there is a strategy for the two provers, that satisfies more than a 2−γ` -fraction of the constraints
in R.
Note that the original graph H has at most nĉ` 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 Y ES -I NSTANCE, 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
S
the end of the algorithm:
|R| |R| |R|
∑ |E(H 0 )| ≥ (`2 α 2 /c0 )O(log n) = (`16 · (α ∗ )2 · log14 n)O(log n) = (α ∗ )O(log n) .
H 0 ∈H2
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 22
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
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 all these strategies,
we can satisfy more than |R|/2γ` constraints of R, contradicting the fact that G is a N O -I NSTANCE.
Running time and the hardness factor. It is easy to see that the algorithm has at most nO(`) iterations,
where in every iteration it processes a distinct active cluster H 0 ⊆ H. The corresponding graph L(H 00 )
has at most nO(`) edges, and so the resulting instance of NDP-Grid contains at most nO(`) vertices.
Therefore, the overall running time of the algorithm is nO(`) . From the above analysis, the algorithm
always correctly classifies G as a Y ES -I NSTANCE or as a N O -I NSTANCE. 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.
1−2/(p+1) (1−ε)
Setting ` = log p n for a large enough integer p, we obtain α ∗ = 2Θ((log N) ) , giving us a 2(log n) -
hardness of approximation for NDP-Grid for any constant ε, assuming NP 6⊆ DTIME(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⊆ DTIME(2n ) for some
constant δ > 0.
Note that the approximation factor α ∗ is in fact eventually expressed as a function of the size of the NDP-
Grid instance, and that we apply the approximation algorithm to instances of NDP-Grid of various sizes.
However, the size of each resulting instance of NDP-Grid is bounded by N, and so the approximation
factor achieved for each such instance should be at most α ∗ (as defined with respect to N).
5.1 Proof of Theorem 5.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 ). Let R00 ⊆ R0 be the set of all constraints R with e(R) ∈ E(H 00 ). Denote
the solution to the (r,h)-GPwB instance I(H 0 ) by ((W1 , . . . ,Wr ), (E1 , . . . , Er )), and let E 0 = ri=1 Ei . Recall
S
that for each random string R ∈ R00 , there is a set E(R) of 12` edges in graph L(H 00 ) 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 ∈ R00 is good if E 0 contains at least 6` /(2α) edges of E(R), and we say that it is
bad otherwise.
Observation 5.4. At least |R0 |/(2α) random strings of R00 are good.
Proof. A good random string contributes at most 6` edges to E 0 , while a bad random string contributes
at most 6` /(2α) edges. If the number of good random strings is less than |R0 |/(2α), then a simple
accounting shows that |E 0 | < |R0 | · 6` /α = |E(H 0 )| · 6` /α, a contradiction.
Consider some random string R ∈ R00 , and assume that R = (QE , QV ). We denote by E 0 (R) = E(R) ∩ E 0 .
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 23
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
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 5.5. Given a random string R ∈ R00 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 5.6. For each good random string R ∈ R00 , 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 if |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` /(8α) is identical, and relies on the fact that |S(QE )| =
6` .
We will use the following simple observation.
Observation 5.7. Let R ∈ R00 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 v j (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.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 24
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
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,
|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 ∈ R00 , 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 ) ∈ R00 if |Wi ∩ S(QE )|, |Wi ∩
S(QV )| > z. We say that an edge e ∈ E 0 (R) is heavy if it belongs to set Ei , where Wi is a heavy cluster for
R. Finally, we say that a random string R ∈ R00 is heavy if 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 strategy for the
provers to choose assignments to the queries, so that at least a 2−γ`/2 -fraction of the constraints in R0
are satisfied. 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. Therefore, for all 1 ≤ i ≤ r,
|Ei0 | ≤ h < z/(8α) must hold, 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 ⊆ R00 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 describe
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 v j (Q, A)). We then choose one of the answers from A(Q) uniformly at random, and
assign it to Q. If A(Q) = 0, / 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 v j (QV , A0 ), and that e ∈ Ei . We say that edge e is happy if 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` z2 α). 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 ) ∩Wi | ≤ z, or |S(QV ) ∩Wi | ≤ z. Assume without loss of generality
that it is the former; the other case is symmetric. Then, since e is not terrible, from Observation 5.7,
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 25
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
|S(QV ) ∩ Wi | ≤ 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αz2 ), and overall, the probability that a fixed
constraint R ∈ L is satisfied is at least |E L (R)|/(8 · 6` z2 α) ≥ 1/(64z2 α 2 ) ≥ 4α/2γ`/2 , since z = 2γ`/8 ,
and α < 2γ`/32 .
So far, we have defined a randomized strategy for the provers that satisfies at least a 2−γ`/2 -fraction of
the constraints in R0 in expectation. We can turn this strategy into a deterministic one, that satisfies at
least a 2−γ`/2 -fraction of the constraints in R0 , using standard techniques: first, for every cluster Wi , we
can compute the expected number of satisfied constraints if the index i is chosen, and then fix the cluster
Wi that maximizes this expectation. The randomized strategy of the provers outlined above can then be
turned into a deterministic one using the method of conditional expectation, as sketched in Section 2.
Case 2. This case happens if at least half of the good random strings are heavy. Let RH ⊆ R00 be the set
of all random strings that are good and heavy, so |RH | ≥ |R0 |/(4α). For each such random string R ∈ RH ,
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 ∈ RH and assume that R = (QE , QV ). For each 1 ≤ i ≤ r, let Ei (R) =
E H (R) ∩ Ei . Recall that, if Ei (R) 6= 0,
/ then |Wi ∩ S(QE )|, |Wi ∩ S(QV )| ≥ z must hold, and, from the
definition of terrible clusters, |Ei (R)| ≥ z/(8α). It is also immediate that |Ei (R)| ≤ |E 0 (R)| ≤ 6` .
In the remainder of the algorithm and its analysis, it would be convenient for us if the values |Ei (R)|
were roughly the same for all indices 1 ≤ i ≤ r and random strings R ∈ RH with Ei (R) 6= 0. / This can
S H
be achieved by discarding all but a polylogarithmic fraction of edges in R∈RH E (R), using standard
geometric grouping and averaging techniques, which we do next.
Consider some heavy random string R ∈ RH . 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 C j (R) iff 2 j−1 < |E H (R) ∩ Ey | ≤
2 j . Then there is some index jR , so that ∑y∈C jR (R) |E H (R) ∩ Ey | ≥ |E H (R)|/ log(6` ). We say that R
chooses the index jR . Notice that:
|E H (R)| 6`
∑ |E H (R) ∩ Ey | ≥ ≥ .
y∈C jR (R)
log(6` ) 8`α log 6
Moreover,
|E H (R)| 6`
|C jR (R)| ≥ ≥ . (5.1)
log(6` ) · 2 jR 8 · 2 jR · `α log 6
Let j∗ be the index that was chosen by at least |RH |/ log(6` ) random strings, and let R∗ ⊆ RH be the set
of all random strings that chose j∗ .
We now proceed in two steps. In the first step, we show a randomized algorithm for computing a collection
H of subgraphs of H 0 . In the second step, we derandomize this algorithm using the method of conditional
expectation.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 26
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
Randomized algorithm. We now show a randomized algorithm to construct a collection
H = {H1 , . . . , H6` }
of subgraphs 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 00 , add the vertex v(Q) to set V (Hi ), where i is the smallest
∗
index for which Wi contains at least 2 j −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 ∈ C j∗ (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 analyze their
properties. It is immediate to verify that the graphs in H are disjoint.
Claim 5.8. 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 ∈ C j∗ (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 00 )|/2γ`/8 ≤
8α|E(H 0 )|/2γ`/8 ≤ |E(H 0 )|/2γ`/16 , since α ≤ 2γ`/32 .
0
Claim 5.9. E [∑ri=1 |E(Hi )|] ≥ 128`|E(H )|
2 α 2 log2 6 .
Proof. Recall that |R∗ | ≥ |RH |/ log(6` ) ≥ |R0 |/(4α log(6` )). We now fix R ∈ R∗ and analyze the proba-
bility that e(R) ∈ ri=1 E(Hi ). Assume that R = (QE , QV ). Let J be the set of indices 1 ≤ y ≤ 6` , such that
S
∗ ∗
|Wy ∩ S(QV )| ≥ 2 j −1 . Clearly, |J| ≤ 6` /2 j −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 |Wy ∩ S(QE )| ≥ 2 j −1 . As before, |J 0 | ≤ 6` /2 j −1 , and
v(QE ) may only belong to graph Hi if i ∈ J. Observe that every index y ∈ C j∗ (R) must belong to J ∩ J 0 ,
and, since j∗ = jR , from Equation (5.1),
6`
|C j∗ (R)| ≥ j∗
.
8 · 2 · `α log 6
Let y ∈ J ∪ J 0 be the first index that occurs in our random ordering. If y ∈ C j∗ (R), then edge e(R) is added
to Hy . The probability of this happening is:
∗
|C j∗ (R)| 6` /(8 · 2 j · `α log 6) 1
0
≥ ` j ∗ −1 = .
|J ∪ J | 2 · 6 /2 32`α log 6
Overall, the expectation of ∑ri=1 |E(Hi )| is at least:
|R∗ | |R0 | |E(H 0 )|
≥ = .
32`α log 6 128`2 α 2 log2 6 128`2 α 2 log2 6
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 27
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
Deterministic algorithm. We obtain a deterministic algorithm for computing a collection H of sub-
graphs of H 0 with the desired properties, by applying the method of conditional expectation. Specifically,
we perform r iterations, where in the ith iteration we choose one of the clusters W j , for 1 ≤ j ≤ r, to be
the ith cluster in the ordering. Notice that Claim 5.8 holds regardless of the ordering of the clusters that
we choose. Therefore, it is sufficient to choose the ordering in such a way that, for the resulting subgraphs
H1 , . . . , Hr ,
r
|E(H 0 )|
∑ |E(Hi )| ≥ 128`2 α 2 log2 6 .
i=1
Consider the first iteration. We process every cluster W j in turn, and compute the expected value of
∑ri=1 |E(Hi )|, if W j is chosen to be the first cluster in the ordering, and the order of the remaining clusters
is random. Once W j is chosen to be the first cluster, the graph H1 if fixed, so we can compute |E(H1 )|
directly. For every random string R ∈ R∗ with e(R) 6∈ E(H1 ), we can calculate the probability that e(R) is
S
included in i>1 E(Hi ) using the same analysis as in Claim 5.9. We then choose a cluster W j that gives
the largest expectation of ∑ri=1 |E(Hi )|, make W j the first cluster in the ordering, and continue to the next
iteration. It is easy to verify that, if {H1 , . . . , Hr } is the final collection of subgraphs of H 0 , then
r
|E(H 0 )|
∑ |E(Hi )| ≥ 128`2 α 2 log2 6 .
i=1
Lastly, the final set H of clusters contains all connected components of every graph in {H1 , . . . , Hr }. It is
now easy to verify that H has all required properties.
6 Reduction from (r,h)-GPwB to NDP-Grid
In this section we prove Theorem 4.3, 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 , |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 also assume that I is a
(d, d 0 , b)-regular instance, for some d, d 0 , b > 0, so for every vertex v ∈ V1 ∪V2 , every bundle B ∈ B(v) has
cardinality b, and graph G̃ is (d, d 0 )-semiregular. We start by describing the construction of the NDP-Grid
instance from the instance I of (r,h)-GPwB.
6.1 Proof intuition
In this section, we assume that we are given an instance I of (r,h)-GPwB as described above, and we
show how to construct a corresponding instance of the NDP-Grid problem. Before we provide a formal
description of the construction, we provide intuition for it. In our construction, the graph Ĝ associated
with the NDP-Grid instance that we are constructing is simply a large enough square grid. We select two
rows of this grid, denoted by R0 and R00 , that are far enough from each other and from the top and bottom
grid boundaries. Consider now the graph G̃ = (V1 ∪ V2 , E) associated with the input instance I of the
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 28
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
(r,h)-GPwB problem. We will associate, with every vertex vi ∈ V1 , a contiguous subpath Ki of the row R0 ,
that we call a block representing vi , such that all resulting subpaths Ki are far from each other, and far
from the grid boundaries. Similarly, we associate, with every vertex v0j ∈ V2 , a subpath K 0j of row R00 , such
that all resulting subpaths K 0j are far from each other and far from the grid boundaries. Intuitively, for
every edge e = (vi , v0j ) ∈ E of graph G̃, with vi ∈ V1 and v0j ∈ V2 , we would like to create a demand pair
s(e),t(e), where s(e) is a vertex lying on Ki , and t(e) is a vertex lying on K 0j . Let us assume for now that
we create these demand pairs in such a way that they do not share source or destination vertices. If we
now consider some block Ki corresponding to some vertex vi ∈ V1 , then we need to designate some of its
vertices as the source vertices s(e) for all edges e ∈ E(G̃) that are incident to vi . For convenience, denote
the set of all edges incident to vi in G̃ by {e1 , . . . , ez }. Notice that for each such edge ez0 , its destination
vertex t(ez0 ) lies in a distinct block K 0jz0 . Therefore, the ordering of the destination vertices is fixed, once
we fix the ordering of the blocks {K 0j }Nj=1
2
along the row R00 . In order to make the routing of these demand
pairs easier, it is convenient to place the source vertices s(e1 ), . . . , s(ez ) on the path Ki in exactly the same
order as the order of their destination vertices on the row R00 . Also, we need to select the spacing between
these source vertices carefully: if the sources are too far apart, then it is easy to show that we can always
route all demand pairs, regardless of whether the corresponding (r,h)-GPwB instance has a high-value
solution or not. On the other hand, if the source vertices are too close to each other, then routing the
demand pairs, in the case where (r,h)-GPwB has a perfect solution can be challenging. The placement of
the destination vertices in blocks K 0j is done similarly.
At a high level, if we assume that the resulting NDP-Grid instance has a large solution value, then we can
define a large subgraph G0 ⊆ G̃ that can be drawn in the plane with relatively few crossings. Graph G0 will
contain all edges e ∈ E(G̃), whose corresponding demand pair is routed by the solution to the NDP-Grid
problem instance. It is well known that graphs that can be drawn in the plane with few crossings have
balanced cuts of a small value (that is, a partition of the vertices of the graph into two subsets of similar
size with only a small number of vertices in each subset that have a neighbor in the other subset). We
exploit this in order to iteratively compute balanced cuts in G0 , until we obtain a partition of G0 into r
clusters, thus obtaining a solution to the underlying (r,h)-GPwB problem. There are two subtleties with
this part of the proof. First, we can only ensure that a drawing of G0 with few crossings exists if the
distances between the source vertices within each block Ki are small enough, and the same holds for the
destination vertices. Second, we are not guaranteed that the resulting solution to the (r,h)-GPwB problem
obeys the bundle condition: that is, it is possible that several edges that belong to the same bundle are
added to the solution. In order to overcome the latter problem, we slightly modify the construction of the
NDP-Grid instance, by unifying some source vertices and some destination vertices, so that, whenever
two edges lie in the same bundle, their corresponding demand pairs share their source or destination
vertex. This ensures that no two edges of the graph G0 induced by the solution to the NDP-Grid problem
instance lie in the same bundle, and that the final solution to the (r,h)-GPwB problem instance is indeed a
feasible solution.
Lastly, we show that, if the instance I of (r,h)-GPwB has a perfect solution, then there is a solution to
the NDP-Grid problem that routes a large enough number of demand pairs. Intuitively, given a perfect
solution ((W1 , . . . ,Wr ), (E1 , . . . , Er )) to the (r,h)-GPwB problem instance, we will route a large subset of
the demand pairs corresponding to the edges in the sets E1 , . . . , Er . Due to the large distances between
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 29
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
the blocks {Ki }vi ∈V1 and between the blocks {K 0j }v0j ∈V2 , in a sense, we can think about routing r different
sets of demand pairs (where each set corresponds to the edges in a distinct set Ei ) independently, and
exploit the large distances between the blocks in order to combine these routings together. There are two
crucial properties that the routing uses. First, we use the fact that within each block Ki , the source vertices
are ordered in the same order as their corresponding destination vertices on row R00 , and the same holds
for each block K 0j ⊆ R00 . Second, we exploit a “distance property,” that, intuitively (though somewhat
imprecisely) says that, if M0 is the set of the demand pairs that we attempt to route, then for any pair
(s(e),t(e)), (s(e0 ),t(e0 )) ∈ M0 of demand pairs, the total number of destination vertices of the pairs in M0
lying between t(e) and t(e0 ) is at most the distance between s(e) and s(e0 ) on row R0 . In order to achieve
this distance property, we will carefully select an ordering of the blocks K10 , . . . , KN0 2 that correspond to
the vertices of V2 along the row R00 . More precisely, we will fix an arbitrary ordering ρ of the groups in
U1 , and we will carefully select an ordering ρ 0 of the groups in U2 . The former will be used in order to
select an ordering of the blocks Ki along the row R0 , while the latter will be used to determine an ordering
of the blocks K 0j along the row R00 .
6.2 The construction
We now proceed to describe the reduction formally. We assume for now that we are given some ordering ρ
of the groups in U1 , and some ordering ρ 0 of the groups in U2 ; we show later how to select these orderings.
Using the ordering ρ, 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 σ . We then define an orderingσ 0 of the vertices of V2
in exactly the same manner, using the ordering ρ 0 of U2 . We assume that V2 = v01 , v02 , . . . , v0N2 , where
the vertices are indexed according to their ordering in σ 0 .
Consider some vertex v ∈ V1 . Recall that B(v) denotes the partition of the edges incident to v in G̃ into
bundles, where every bundle is a non-empty subsets of edges, and that β (v) = |B(v)|. Recall also that,
since graph G̃ is (d, d 0 )-semiregular, d ≤ dG̃ (v) < 2d. Moreover, since every bundle has cardinality b, we
get that for every vertex v ∈ V1 :
d/b ≤ β (v) < 2d/b. (6.1)
Recall also that, since instance I is valid, ∑v∈V1 β (v) = β ∗ (I) = hr. As every bundle contains exactly b
edges, we get that:
|E(G̃)| = ∑ d(v) = ∑ β (v) · b = hrb. (6.2)
v∈V1 v∈V1
Consider again some vertex v ∈ V1 . Recall that each 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). For every bundle B ∈ B(v), we
say that the corresponding group U(B) ∈ U2 covers v.
The ordering ρ 0 of the groups in U2 naturally induces an ordering of the bundles in B(v), where B appears
before B0 in the ordering iff U(B) appears before U(B0 ) in ρ 0 . We denote
B(v) = B1 (v), B2 (v), . . . , Bβ (v) (v) ,
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 30
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
where the bundles are indexed according to this ordering.
Similarly, for a vertex v0 ∈ V2 , every bundle B ∈ B(v0 ) corresponds to a group U(B) ∈ U1 , and contains
all edges that connect v0 to the vertices of U(B). As before, the ordering ρ of the groups in U1 naturally
defines an ordering of the bundles in B(v0 ). We denote B(v0 ) = B1 (v0 ), B2 (v0 ), . . . , Bβ (v0 ) (v0 ) , and we
assume that the bundles are indexed according to this ordering.
Lastly, since graph G̃ is (d, d 0 )-semiregular, we get that |E(G̃)| ≥ d 0 N2 /(4 log N2 ) ≥ d 0 N2 /(4 log M).
Since every group in U2 contains exactly r vertices of V2 , we get that:
N2 4|E(G̃)| log M
|U2 | = ≤ . (6.3)
r d0r
We are now ready to define the instance Î = (Ĝ, M) of NDP-Grid, from the input instance (G̃ =
(V1 ,V2 , E), U1 , U2 , h, r) of (r,h)-GPwB. Let λ = 2048 · M 2 · log M . The graph Ĝ is simply the (λ × λ )-
grid, so V (Ĝ) = O(M 4 log2 M) as required. We now turn to define the set M of the demand pairs. We
first define the set M itself, without specifying the locations of the corresponding vertices in Ĝ, and later
specify a mapping of all vertices participating in the demand pairs to V (Ĝ).
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 v0 ∈ V2 ,
for every bundle B0 ∈ B(v0 ), we unify all destination vertices t(e) with e ∈ B0 into a single destination
vertex, that we denote by tB0 , 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) ,tB0 (e) ), where B(e) and B0 (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) ,tB0 (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 Ĝ. Let R0 and R00 be two rows of the grid Ĝ, lying at a distance at least λ /4 from
each other and from the top and the bottom boundaries of the grid, with R0 lying above R00 . We will map
all vertices of S(M) to R0 , and all vertices of T (M) to R00 , as follows.
Locations of the sources. Let K1 , K2 , . . . , KN1 be a collection of N1 disjoint subpaths of R0 , where each
subpath contains 1024 · dh · log Me vertices; the subpaths 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 Ĝ. Observe that the width λ of the grid is large enough
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 31
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
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 , so that they appear on Ki in this order, and every
i
consecutive pair of sources is separated by exactly 512 · dh · log M/β (vi )e vertices.
Locations of the destinations. Similarly, we let K10 , K20 , . . . , KN0 2 be a collection of N2 disjoint subpaths
of R00 , each of which contains 1024 · dh · log Me vertices, so that the subpaths 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 Ĝ. We call Ki0 the block representing
the vertex v0i ∈ V2 . We now fix some 1 ≤ i ≤ N2 and consider the block Ki0 representing the vertex v0i . We
map the destination vertices
tB1 (v0i ) ,tB2 (v0i ) , . . . ,tBβ (v0 ) (v0i )
i
to vertices of Ki0 , so that they appear on Ki0 in this order, and every consecutive pair of destinations is
separated by exactly 512 · dh · log M/β (v0i )e vertices.
This concludes the definition of the instance Î = (Ĝ, M) of NDP-Grid, except for the procedure for
selecting the orderings ρ and ρ 0 of the groups in U1 and U2 , respectively. The following immediate
observation will be useful to us.
Observation 6.1. Consider a vertex v j ∈ V1 , and let N j ⊆ M be any subset of demand pairs, whose
sources are all distinct and lie on K j . Assume that N j = {(s1 ,t1 ), . . . , (sy ,ty )}, where the demand pairs
are indexed according to the left-to-right ordering of their source vertices on K j . Then t1 , . . . ,ty appear in
this left-to-right order on R00 .
Choosing the orderings of the groups. We now show an algorithm for selecting the ordering ρ of U1
and ρ 0 of U2 that are used in the reduction. We let ρ be an arbitrary ordering of the groups in U1 . Before
we describe an algorithm for computing the ordering ρ 0 of U2 , we first define the properties that we need
from it.
Assume that we are given some ordering ρ 0 over the groups in U2 . Consider first some vertex vi ∈ V1 ,
and recall that we have denoted its bundles by B1 (vi ), . . . , Bβ (vi ) . Recall that every bundle B j (vi ) contains
all edges connecting vi to a single group of U2 , that we denote, for convenience, by U ji . We assume that
the bundles are indexed so that U1i , . . . ,Uβi i (vi ) appear in ρ 0 in this order. Recall that, from Equation (6.1),
d/b ≤ β (vi ) < 2d/b. Intuitively, we will only focus on the first dd/(2b)e bundles of vi , and we will never
attempt to route demand pairs that correspond to the remaining bundles. We say that vertex vi is happy
with the ordering ρ 0 of U2 , if, for all 1 ≤ j < dd/(2b)e, the total number of groups that appear strictly
between U ji and U ji+1 in ρ 0 is at most
|U2 |b log2 M
O
d
(notice that the indexing of the bundles B j (vi ) and of the corresponding groups U ji depends on ρ 0 ). We
say that ordering ρ 0 is good if every vertex vi ∈ V1 is happy with this ordering. Intuitively, choosing an
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 32
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
ordering ρ 0 that is good will ensure that the distance property mentioned above holds, which will allow
us to route a large set of the demand pairs in the case where there is a perfect solution to the (r,h)-GPwB
instance. We now show that we can compute such an ordering ρ 0 efficiently.
Lemma 6.2. There is an algorithm whose running time is polynomial in |V (G̃)|, that computes a good
ordering ρ 0 of U2 .
compute a partition U , U , . . . , U of U2 into subsets, each of which has
Proof. The algorithm will 1 2 q
|U2 |b log2 M
cardinality O d . In the final ordering ρ 0 , groups of U2 that lie within a single set Ui are placed
consecutively, in an arbitrary order, while groups lying in different sets are ordered according to the
ordering U1 , U2 , . . . , Uq of these sets.
The algorithm consists of a number of iterations, where in the ith iteration we compute the subset Ui ⊆ U2
of groups. We now describe a single iteration. Recall that for every vertex v ∈ V1 , we have defined a
collection of groups that cover v—these are all groups U ∈ U2 such that there is a bundle B ∈ B(v),
connecting v to vertices of U. The total number of groups that cover v is β (v) ≥ d/b from Equation
6.1. We say that vertex v is active in iteration i if the number of groups that cover u and belong to
U1 ∪ · · · ∪ Ui−1 is less than dd/(2b)e. Let U0 = U2 \ (U1 ∪ · · · ∪ Ui−1 ), and let V 0 ⊆ V1 be the set of all
vertices that are active in iteration i. Recall that by the definition of active vertices, for each v ∈ V 0 , there
in U that cover v. We next show that we can efficiently compute a subset
are at least d/(2b) groups 0
2
Ui ⊆ U2 of O |U2 |bdlog M groups, such that for every active vertex v ∈ U0 , at least one group in Ui covers
v. Note that, if we manage to select the groups U1 , U2 , . . . , Uq with this property, such that i Ui = U2 ,
S
then it is immediate to verify that the resulting ordering ρ 0 of U2 is a good ordering. This is since, for
every vertex v ∈ V1 , if v was active for i iterations, then U1 ∪ · · · ∪ Ui contain at least dd/(2b)e groups
0
that cover v, and every set Ui for 1 ≤ i0 ≤ i contains at least one such group. The following claim will
then complete the proof of the lemma.
Claim 6.3. There is an efficient algorithm, that, given an integer i > 0, collections U1 , . . . , Ui−1 of subsets
of U2 , and the set V 0 ⊆ V1 of vertices
that are
0
active in iteration i, such that V 6= 0,
/ computes a collection
|U |b log M
U ⊆ U2 \ (U ∪ · · · ∪ U ) of O
i 1 i−1 2
d groups, such that for every active vertex v ∈ U0 , at least one
group in Ui covers v.
Proof. For convenience, we denote U0 = U2 \ (U1 ∪ · · · ∪ Ui−1 ). The algorithm exploits the Set Cover
problem. In this problem, we are given as input a collection {1, . . . , n} of elements, and a collection
S = {S1 , . . . , Sm } of subsets of elements, so for all 1 ≤ j ≤ m, S j ⊆ {1, . . . , m}. The goal is to compute
a minimum cardinality collection S0 ⊆ S of subsets, such that every element in {1, . . . , n} belongs to at
least one subset in S0 . We use the following observation, whose proof appears in the Appendix.4
Observation 6.4. There is an efficient algorithm, that, given an instance of the Set Cover problem with n
elements and m sets, such that every element belongs to at least m/t sets, computes a solution containing
at most O(t log n) sets.
4 This proof was suggested to us by one of the reviewers of the paper. A previous version of the paper contained a slightly
weaker proof.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 33
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
In order to complete the proof of Claim 6.3, we set up an instance of the Set Cover problem, where every
group in U0 represents a set, every vertex in V 0 is an element, and element v ∈ V 0 belongs to a set SU
representing a group U ∈ U0 if and only if U covers v. Recall that we are guaranteed that every element
belongs to at least d/(2b) sets. Setting t = |U0 | · (2b)/d, and using the algorithm from Observation 6.4,
we obtain a solution to the resulting instance of the Set Cover problem of value
|U2 |b log N1 |U2 |b log M
O ≤O ,
d d
which immediately defines the desired set Ui ⊆ U0 of groups.
Our algorithm employs Claim 6.3 to construct the sets U1 , U2 , . . . of groups, until the set V
0 of vertices
that are active becomes empty. Each subsequent set Ui then contains an arbitrary subset of O |U2 |bdlog M
groups of U2 \ (U1 ∪ · · · ∪ Ui−1 ).
This concludes the description of the reduction from (r,h)-GPwB to NDP-Grid. In order to complete the
proof of Theorem 4.3, it is now enough to prove the following two theorems, which is done in the next
two subsections.
Theorem 6.5. Let I = (G̃ = (V1 ,V2 , E), U1 , U2 , h, r) be a valid and (d, d 0 , b)-regular instance of (r,h)-
GPwB such that I has a perfect solution. Then there is a solution to instance Î of NDP-Grid, routing
Ω(β ∗ (I)/ log2 M) demand pairs via a set of spaced-out paths.
Theorem 6.6. There is an efficient algorithm, that, given a valid and (d, d 0 , b)-regular instance I =
(G̃ = (V1 ,V2 , E), U1 , U2 , h, r) of the (r,h)-GPwB problem with |E| = M, the corresponding instance Î of
NDP-Grid, and a solution P∗ to Î, computes a solution to the (r,h)-GPwB instance I of value at least
Ω(|P∗ |/ log3 M).
6.3 From partitioning to routing: proof of Theorem 6.5
The goal of this subsection is to prove Theorem 6.5.
Let ((W1 , . . . ,Wr ), (E1 , . . . , Er )) be a perfect solution to instance I of (r,h)-GPwB. 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.
We let E 0 = ri=1 Ei , so |E 0 | = β ∗ (I) = hr. Let M0 ⊆ M be the set of all demand pairs corresponding
S
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. We now define a slightly smaller subset
E 1 ⊆ E 0 of edges, and a corresponding set M1 ⊆ M0 of demand pairs. Since the value of the solution
((W1 , . . . ,Wr ), (E1 , . . . , Er )) of the (r,h)-GPwB problem instance is hr = β ∗ (I) = ∑v∈V1 β (v), for every
vertex v ∈ V1 , there are exactly β (v) edges in E 0 —one edge from each bundle B ∈ B(v). Recall that the
total number of such bundles is β (v) < 2d/b from Equation (6.1). Recall that every bundle B ∈ B(v)
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 34
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
corresponds to a distinct group U(B) ∈ U2 , that covers v. Moreover, we have used the ordering ρ 0 of
the groups in U2 in order to define an ordering of the bundles in B(v). Let {ei1 , . . . , eiβ (vi ) } be the set of
all edges of E 0 that are incident to vertex vi . We assume that these edges are indexed according to the
ordering of their corresponding bundles. We discard all but the first dd/(2b)e edges from this set. We
then denote by E 1 ⊆ E 0 the resulting set of edges, obtained after processing every vertex in V1 . It is easy
to verify that |E 1 | = Ω(|E 0 |). We let M1 ⊆ M0 be the set of all demand pairs corresponding to the edges
of E 1 .
Assume now that we are given any subset M0 ⊆ M1 of demand pairs. We define an ordering η(M0 )
of the demand pairs in M0 , by exploiting the perfect solution ((W1 , . . . ,Wr ), (E1 , . . . , Er )) to instance
I of (r,h)-GPwB, as follows. Recall that every demand pair (s,t) ∈ M1 corresponds to some edge
e ∈ E1 ∪ · · · ∪ Er , that we denote by e(s,t). First, we partition the demand pairs in M0 into subsets
M01 , . . . , M0r , as follows: demand pair (s,t) ∈ M0 is added to subset M0i iff the corresponding edge e(s,t)
lies in Ei . The demand pairs that lie in different sets M01 , . . . , M0r are then ordered according to the natural
order of these sets. Consider now some set M0i of demand pairs. We order the demand pairs in M0i
according to the left-to-right order of their destination vertices on row R00 . Let η(M0 ) be the resulting
ordering of the demand pairs in M0 . Next, we define a property of a subset of the demand pairs, called a
distance property. We later show that, if we are given a subset M0 ⊆ M1 of demand pairs that has the
distance property, then all demand pairs in M0 can be routed via spaced-out paths. We also show that
there is a large subset M0 ⊆ M1 of the demand pairs that has the the distance property.
We now proceed to define a distance property. We assume that we are given a set M0 ⊆ M1 of demand
pairs,
and consider the corresponding ordering η = η(M0 ) of these demand pairs. We denote M0 =
(s1 ,t1 ), . . . , (s|M0 | ,t|M0 | ) , where the demand pairs are indexed according to their ordering in η. Notice
that this ordering is not necessarily the same as the ordering of the set S(M0 ) of source vertices on row R0 ,
or the ordering of the set T (M0 ) of the destination vertices on row R00 .
Consider some pair s, s0 ∈ S(M0 ) of source vertices, and assume that s = si and s0 = s j . We denote
NM0 (s, s0 ) = |i − j| − 1—the number of the demand pairs in the ordering η, that lie between (si ,ti ) and
(s j ,t j ).
Definition 6.7. Given a set M0 ⊆ M1 of demand pairs, we say that two source vertices s, s0 ∈ S(M0 ) are
consecutive with respect to M0 if s 6= s0 , and no vertex of S(M0 ) lies strictly between s and s0 on row
R0 . We say that M0 has the distance property if for every pair s, s0 ∈ S(M0 ) of source vertices that are
consecutive with respect to M0 , NM0 (s, s0 ) < d(s, s0 )/4 holds, where d(s, s0 ) is the distance between s and
s0 in graph Ĝ.
In order to complete the proof of Theorem 6.5, we proceed in two steps. First, we show that there is a
large enough subset M0 ⊆ M1 of demand pairs that has the distance property. Next, we show that any
such set M0 of demand pairs can be routed via spaced-out paths.
Lemma 6.8. There is a subset M0 ⊆ M1 of demand pairs that has the distance property, and |M0 | =
Ω(|M1 |/ log2 M) = Ω(|M0 |/ log2 M).
Lemma 6.9. Assume that M0 ⊆ M1 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 Ĝ.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 35
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
The above two lemmas finish the proof of Theorem 6.5, since |M0 | = β ∗ (I). We prove these lemmas in
the following two subsections.
6.3.1 Proof of Lemma 6.8
Let η 1 = η(M1 ) be the ordering of the demand pairs in M1 . We show that this ordering almost has the
distance property: if s, s0 are two consecutive sources with respect to M1 , then NM1 ≤ O(d(s, s0 ) log2 M)
holds. We then use a simple procedure in order to select a subset M0 ⊆ M1 of Ω(|M1 |/ log2 M) demand
pairs that has the distance property.
Analyzing ordering η 1 . Recall that ordering η 1 of the demand pairs in M1 was defined using the
perfect solution ((W1 , . . . ,Wr ), (E1 , . . . , Er )) to instance I of (r,h)-GPwB. We have partitioned the demand
pairs in M1 into subsets M1 , . . . , Mr , by using the partition {E1 , . . . , Er } of their corresponding edges.
The demand pairs that lie in different sets M1 , . . . , Mr are then ordered according to the natural order of
these sets, while the demand pairs in each set Mi are ordered according to the left-to-right order of their
destination vertices on row R00 . We need the following claim.
Claim 6.10. Let s, s0 ∈ S(M1 ) be any pair of source vertices that are consecutive with respect to M1 .
Then NM1 (s, s0 ) ≤ O(d(s, s0 ) log2 M).
Proof. First, if s and s0 belong to distinct blocks Ki on row R0 , then, since the distance between every
pair of blocks is at least M, while |M1 | ≤ M, the assertion clearly holds. Therefore, we can assume that
there is some block Ki , with s, s0 ∈ Ki . Recall that block Ki represents vertex vi ∈ V1 . Assume w.l.o.g. that
vi ∈ W j , in the solution to the (r,h)-GPwB problem.
Let (s,t), (s0 ,t 0 ) ∈ M1 be the demand pairs corresponding to these source vertices; the demand pairs are
uniquely defined, since the pairs in M1 do not share their source or their destination vertices. Let e be
the edge of G̃ corresponding to the demand pair (s,t), and let e0 be the edge of G̃ corresponding to the
demand pair (s0 ,t 0 ). Then e and e0 are both incident to the vertex vi , and they lie in distinct bundles of
B(vi ). Recall that we have used the ordering ρ 0 of the groups in U2 in order to define an ordering of
β (v )
the bundles in B(vi ), which we used in turn in order to define an ordering {e1i , . . . , ei i } of the edges
incident to vi that belong to E 0 . Only the first dd/(2b)e of these edges were added to E 1 . Moreover, since
the solution to instance I of (r,h)-GPwB that we have considered is perfect, every bundle incident to
vi contributed exactly one edge to E 0 . Therefore, if we denote e = ezi , then e0 = ez+1
i (or the other way
around; we assume it is the former), and z + 1 ≤ dd/(2b)e. Let U ∈ U2 be the group corresponding to
the bundle of e; that is, e connects vi to a vertex of U. Let U 0 be defined similarly to edge e0 . From our
definition of a good ordering, there are at most O(|U2 |b log2 M/d) groups that lie between U and U 0 in
the ordering ρ 0 . We will use this fact in order to bound NM1 (s, s0 ), that we denote, for convenience, by
N(s, s0 ).
Let (s00 ,t 00 ) ∈ M1 be any demand pair that lies between (s,t) and (s0 ,t 0 ) in the ordering η 1 . Then the edge
e00 ∈ E 1 corresponding to this demand pair must also lie in set E j that corresponds to the cluster W j in the
solution to instance I of (r,h)-GPwB, and moreover, t 00 must lie between t and t 0 on row R00 . If t 00 lies in
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 36
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
some block Kx0 , that represents a vertex v0x ∈ V2 , then the group U 00 to which v0x belongs must lie between
U and U 0 in the ordering ρ 0 . Recall that, since ρ 0 is a good ordering of the groups in U2 , there are at most
O(|U2 |b log2 M/d) groups that lie between U and U 0 in the ordering ρ 0 . Let us now consider any such
group U 00 , that consists of r vertices. Exactly one vertex of U 00 lies in W j ; we denote it by v0 (U 00 ). This
vertex has degree at most d 0 in G̃, and so B(v0 (U 00 )) contains at most d 0 /b bundles. Therefore, at most
d 0 /b edges that are incident to v0 (U 00 ) belong to E 1 . Altogether, we conclude that:
0
|U2 |b log2 M
d
N(s, s0 ) ≤ O ·
d b
0 2
|U2 |d log M
≤O
d
|E(G̃)| log3 M
≤O
dr
hb log3 M
≤O .
d
(We have used Equation (6.3) for the penultimate inequality and Equation (6.2) for the last inequality.)
Recall that, from our construction, d(s, s0 ) = 512 · dh · log M/β (vi )e ≥ 256hb log M/d, since, from Equa-
tion (6.1), β (v) < 2d/b. We conclude that NM1 (s, s0 ) ≤ O(d(s, s0 ) log2 M).
We obtain the following immediate corollary of Claim 6.10.
Corollary 6.11. There is a constant c, such that, for any pair s, s0 ∈ S(M1 ) of source vertices (that are
not necessarily consecutive with respect to M1 ), NM1 (s, s0 ) ≤ cd(s, s0 ) log2 M holds.
n o
Defining M0 . We denote M1 = (s1 ,t1 ), . . . , (s|M1 | ,t|M1 | ) , where the demand pairs are indexed ac-
cording to the ordering η 1 . We now let:
M0 = (si ,ti ) | i = 1 mod 8c log2 M .
We let η be the ordering of the demand pairs in M0 , induced by η 1 . It is immediate to verify that
|M0 | = Ω(|M1 |/ log2 M) = Ω(|M0 |/ log2 M), and 2thatη = η(M
0 ). Moreover, if s, s0 ∈ S(M0 ) is any pair
of source vertices, then NM0 (s, s ) ≤ NM1 / 8c log M ≤ d(s, s )/4 from Corollary 6.11. Therefore, M0
0 0
has the distance property.
6.3.2 Proof of Lemma 6.9
Recall that R0 and R00 are the rows of Ĝ 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 Ĝ,
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.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 37
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
We denote M 0 = |M0 |, and M0 = {(s1 ,t1 ), . . . , (sM0 ,tM0 )}, where the pairs are indexed according to their
ordering in η = η(M0 ). To recap, the ordering η of M0 was defined as follows. We have defined a partition
M1 , . . . , Mr of the demand pairs in M0 , according to the partition E1 , . . . , Er of their corresponding edges.
For each 1 ≤ i ≤ r, the demand pairs in Mi appear consecutively in η, ordered according to the left-
to-right ordering of their destination vertices on row R00 , while the order of the demand pairs lying in
different sets Mi follows the indexing of these subsets.
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 Ĝ
into two subgrids: a top subgrid Gt spanned by all rows that appear above R (including R), and a bottom
subgrid 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 P1 routing all pairs in
{(si , xi ) | 1 ≤ i ≤ M 0 } in the top grid Gt , and set P2 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 v j ∈ V1 , and the corresponding block K j . We construct
a subgrid K̂ j of Ĝ, containing K j , that we call a box, as follows. Let C j be the set of all columns of Ĝ
intersecting K j . We augment C j by adding 2M columns lying immediately to the left and 2M columns
lying immediately to the right of C j , obtaining a set Ĉ 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 subgrid
of Ĝ spanned by the rows in R̂ and the columns in Ĉ j . Since every block is separated by at least 10M
columns from every other block, as well as from the left and the right boundaries of Ĝ, the resulting
boxes are all disjoint, and every box is separated by at least 2M columns of Ĝ from every other box, and
from the left and the right boundaries of Ĝ.
We will initially construct a set P1 of spaced-out paths in Gt , such that each path Pi ∈ P1 , for 1 ≤ i ≤ M 0 ,
originates from the vertex xi , and visits the boxes K̂1 , K̂2 , . . . , K̂N1 in this order. 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 6.12. Consider some vertex v j ∈ V1 , and the corresponding box K̂ j . Denote Y j = S(M0 ) ∩V (K j ),
M j = |Y j |, and assume that Y j = {si1 , si2 , . . . , siM j }, where the indexing of the vertices of Y j is consistent
with the indexing of the vertices of S(M0 ) induced by the ordering η of the demand pairs in M0 , and
i1 < i2 < . . . < iM j . Then there is a set W j of M 0 columns of the box K̂ j , such that:
• set W j does not contain a pair of consecutive columns; and
• for each 1 ≤ z ≤ M j , the iz th column of W j from the left contains the source vertex siz .
Proof. Observe that from Observation 6.1, the vertices si1 , si2 , . . . , siM j must appear in this left-to-right
order on R0 , while the vertices xi1 , xi2 , . . . , xiM j appear in this left-to-right order on R. Moreover, for all
1 ≤ z < M j , iz+1 − iz − 1 = NM0 (siz , siz+1 ) ≤ d(siz , siz+1 )/4, from the distance property of M j . We add to
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 38
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
W j all columns of K̂ j where the vertices of Y j lie. For each 1 ≤ z < M j , we also add to W j 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 W j is consecutive. Finally, we add to W j (i1 − 1) columns that lie to the left of the column
of si1 , and (M 0 − iM j ) columns that lie to the right of the column of siM j . We make sure that no pair of
columns in W j is consecutive—it is easy to see that there are enough columns to ensure that.
Claim 6.13. There is a set P1 = {P1 , . . . , PM0 } 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 W j ; in particular, it contains vertex 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 v0j ∈ V2 , and the corresponding block K 0j . We
construct a box K̂ 0j containing K 0j exactly as before. As before, the resulting boxes are all disjoint, and
every box is separated by at least 2M columns of Ĝ from every other box, and from the left and the right
boundaries of Ĝ.
As before, we will initially construct a set P2 of spaced-out paths in Gb , such that each path Pi0 ∈ P2 , for
1 ≤ i ≤ M 0 , originates from the vertex xi , and visits the boxes K̂10 , K̂20 , . . . , K̂N0 2 in turn. We will ensure that
each such path Pi0 contains the corresponding destination vertex ti . Eventually, by suitably truncating each
such path Pi0 , we will ensure that it connects xi to ti .
Claim 6.14. Consider some vertex v0j ∈ V2 , and the corresponding box K̂ 0j . Denote Y j0 = T (M0 ) ∩V (K 0j ),
M 0j = |Y j0 |, and assume that Y j0 = {ti1 ,ti2 , . . . ,tiM0 }, where the indexing of the vertices of Y j0 is consistent
j
with the ordering η = η(M0 ) of the demand pairs in M0 , and i1 < i2 < . . . < iM0j . Then there is a set W0j
of M 0 columns of the box K̂ 0j , such that:
• set W0j does not contain a pair of consecutive columns; and
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 39
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
• for each 1 ≤ z ≤ M 0j , the iz th column of W0j from the left contains the destination vertex tiz .
Proof. From the definition of the ordering η of M0 , the demand pairs (si1 ,ti1 ), (si2 ,ti2 ), . . . , (siM j ,tiM j )
appear consecutively in this order in η. Moreover, from the construction of the NDP-Grid instance
(Ĝ, M), every pair of destination vertices in T (M0 ) is separated by at least one vertex. We add to W0j all
columns in which the vertices ti1 ,ti2 , . . . ,tiM j lie. We also add to W0j i1 − 1 columns that lie to the left of
the column of ti1 , and M 0 − iM0j columns that lie to the right of the column of tiM j in K̂ 0j . We make sure
that no pair of columns in W0j 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 6.13 and is omitted here.
Claim 6.15. There is a set P2 = P10 , . . . , PM0 0 of spaced-out paths in Gb , that are internally disjoint from
R, such that for each 1 ≤ i ≤ M 0 , path Pi0 originates from vertex xi , and for all 1 ≤ j ≤ N2 , it contains the
ith column of W0j ; in particular it contains ti .
By combining the paths in sets P1 and P2 , we obtain a new set P∗ = P1∗ , . . . , PM∗ 0 of spaced-out paths,
such that for all 1 ≤ i ≤ M 0 , 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 .
6.4 From routing to partitioning: proof of Theorem 6.6
In this subsection we conclude the proof of Theorem 4.3, by proving Theorem 6.6. 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 subgraph 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 , . . . ,Wlr ), (E1 , . .m. , Er )), where
∗|
W1 = V (G̃) and W2 = W3 = · · · = Wr = 0;/ set E1 contains an arbitrary subset of 264|P log3 M
≤ h 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 subgraphs, 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.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 40
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
Definition 6.16. Given a graph H and a parameter 0 < ρ < 1, a cut (A, B) of H is called a ρ-edge-balanced
cut if |E(A)|, |E(B)| ≥ ρ · |E(H)|.
The following theorem is central to the proof of Theorem 6.6.
Theorem 6.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 6.17 below, after we complete the proof of Theorem 6.6 using it. Our algorithm
maintains a collection G of disjoint vertex-induced subgraphs 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 algorithm
continues as long as G contains a graph H ∈ G with |E(H)| > 264 · h log3 M; if no such graph H exists,
then 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 6.17 to it, obtaining
|E(H)|
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.
Claim 6.18. Let G0 be the final set of disjoint subgraphs of G̃0 obtained at the end of the algorithm. Then
∑H∈G0 |E(H)| ≥ Ω(|E(G̃0 )|), and |G0 | ≤ r.
Proof. We construct a binary partitioning tree τ of graph G̃0 , that simulates the graph partitions computed
by the algorithm. For every subgraph H ⊆ G̃0 that belonged to G over the course of the algorithm, tree
τ contains a node v(H). The root of the tree is the node v(G̃0 ). If, over the course of our algorithm, we
have partitioned the graph H into two disjoint vertex-induced subgraphs H0 and H00 , then we add edges
(v(H), v(H0 )) and (v(H), v(H00 )) to the tree, and v(H0 ), v(H00 ) become the children of v(H) in τ.
The level of a node 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 are
1/32−edge-balanced, ∆ ≤ loglog M
(32/31) . Consider now some level 0 ≤ i ≤ ∆, and let Vi be the set of all
nodes of the tree τ lying at level i. Let Vi0 be a set of nodes consisting of all nodes of Vi , and all nodes
that lie at levels 0, . . . , (i − 1) that are leaves of the tree. Let Êi = v(H)∈Vi0 E(H) be the set of all edges
S
contained in all subgraphs H of G̃0 , whose corresponding node v(H) lies in Vi0 . Finally, let mi = |Êi |.
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 log M m0 m0
m0 − m∆ ≤ ≤ · ≤ ,
64 log M log 32/31 64 log M 2
and so ∑H∈G0 |E(H)| = m∆ ≥ m0 /2. This finishes the proof of the first assertion. We now turn to
prove the second assertion. Recall that no two edges of E ∗ may belong to the same bundle. Since
h = β ∗ (I)/r = ∑v∈V1 β (v) /r, for any subset E 0 ⊆ E ∗ of edges, |E 0 | ≤ ∑v∈V1 β (v) ≤ hr must hold, and
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 41
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
in particular, |E ∗ | ≤ hr. It is now enough to prove that for every leaf vertex v(H) of τ, |E(H)| ≥ h
holds—since all graphs in G0 are mutually disjoint, and each such graph corresponds to a distinct leaf of
τ, this would imply that |G0 | ≤ r.
Consider now some leaf vertex v(H) of τ, and let v(H0 ) be its parent. Then |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 |G0 | ≤ r.
We are now ready to define the solution ((W1 , . . . ,Wr ), (E1 , . . . , Er )) to the (r,h)-GPwB problem instance
I. Let G0 be the set of the subgraphs of G̃0 obtained at the end of our algorithm, and denote G0 =
{H1 , H2 , . . . , Hz }. Recall that from Claim 6.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 = 0/ and Ei = 0. / 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 r
∑ |Ei | ≥ ∑ Ω(|E(Hi )|/ log3 M) = Ω(|E(G̃0 )|/ log3 M) = Ω(|P∗ |/ log3 M),
i=1 i=1
from Claim 6.18. In order to complete the proof of Theorem 6.6, it now remains to prove Theorem 6.17.
Proof of Theorem 6.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-edge-balanced 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 6.19. 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 whenever a point x belongs to three such curves, x is an endpoint of all three
curves; 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 6.20. There is an efficient algorithm that, given a solution P∗ to the NDP-Grid problem instance
Î, and a vertex-induced subgraph H ⊆ G̃0 , computes a drawing of H with at most 2048 · |E(H)| dh log Me
crossings.
Proof. We consider the natural embedding of the grid Ĝ into the plane. We will use this drawing of Ĝ in
order to guide our drawing of the graph H. Notice that this embedding of Ĝ naturally defines a drawing
of every path P ∈ P∗ , obtained by taking the union of the images of the edges of P. We will map vertices
of H to points that lie inside some faces defined by the cells of the grid. Consider a vertex vi ∈ V (H) ∩V1 ,
and let Ki be the block representing this vertex. Let κi be any cell of the grid Ĝ 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 v0j ∈ V (H) ∩V2 , we select a cell κ 0j whose
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 42
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
boundary contains a vertex of the corresponding block K 0j , and map v0j 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 , v0j ) ∈ E(H), with
vi ∈ V1 and v0j ∈ V2 , and let (s,t) ∈ M∗ be its corresponding demand pair. Let Ki and K 0j 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 Î. 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 v0j , 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 , v0j ) ∈ E(H) with vi ∈ V1 and v0j ∈ V2 , and let Ki and K 0j be the blocks
representing vi and v0j 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
P0 ∈ P∗ routing the demand pair (s0 ,t 0 ) corresponding to the edge e0 contains a vertex of Ki . Since
|V (Ki )| ≤ 1024 · dh log Me, at most 1024 · dh log Me 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:
∑ 2 · 1024 · dh log Me = 2048 · |E(H)| dh log Me .
e∈E(H)
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 6.21. 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
20
that m > 2 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 6.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)
for all v ∈ V1 ∪ V2 , and so the maximum vertex degree in H is bounded by d = h. From Lemma 6.20,
the drawing ϕ of H has at most 2048|E(H)| dh log Me ≤ 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 6.21 to graph q H to obtain a 1/32-edge-balanced cut (A, B) with
√ p |E(H)|
|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 6.21.
Proof of Lemma 6.21. We start by providing some intuition for the proof. In general, it is well known
that a graph G that can be drawn in the plane with at most cr crossings has a balanced separator (a
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 43
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
Figure 5: Grid Qv obtained from v
p
vertex-cut), containing O( |V (G)| + cr) vertices. However, in our case, we need to compute an edge-cut,
and since some vertex degrees may be quite large, using this bound and then deleting all edges incident
to the vertices in the separator is not sufficient to us. In order to overcome this difficulty, we slightly
transform our graph into a constant-degree graph, and then work with the transformed graph directly.
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 Ĥ from graph H as follows. For every vertex v ∈ V (H), we add a (dv × dv )-grid
Qv to Ĥ, 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 Ĥ, as
follows. Assume that e = ei (v) = e j (u). Then we add an edge (pi (v), p j (u)) to Ĥ. We think of this edge
as the special edge representing e. This finishes the definition of the graph Ĥ. It is immediate to see that
the drawing ϕ of H can be extended to a drawing ϕ 0 of Ĥ 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 Ĥ is 4. We will use the following bound on |V (Ĥ)|:
Observation 6.22. |V (Ĥ)| ≤ 2md.
Proof. Clearly, |V (Ĥ)| = ∑v∈V (H) dv2 ≤ ∑v∈V (H) d · dv ≤ 2md.
Let Ĥ0 be the graph obtained from Ĥ by replacing every intersection point in the drawing ϕ 0 of Ĥ with
a vertex. Then Ĥ0 is a planar graph with |V (Ĥ0 )| ≤ |V (Ĥ)| + cr ≤ 2md + mdα ≤ 4mdα, as α ≥ 1. We
assign weights to the vertices of Ĥ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 [52, 40, 2].
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 44
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
Theorem 6.23 ([40]). There is an efficient algorithm, that, given a planar graph G = (V, E) with 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;
• ∑v∈A w(v), ∑v∈B w(v) ≤ 2W /3; and
√
• |X| ≤ 2 2n.
q
We apply Theorem 6.23 to graph Ĥ0 , to obtain a partition (A, X, B) of V (Ĥ0 ), with |X| ≤ 2 2|V (Ĥ0 )| ≤
√
2 8mdα. Since W = ∑v∈V (Ĥ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 , B0 ) of V (Ĥ0 ) by setting A0 = A∪X and B0 = B. Since |X| ≤ 2 8mdα ≤ m/3 (as m > 220 dα),
we are guaranteed that |A0 ∩ 0 0
√Π|, |B ∩ Π| ≤ 4m/3 holds. Moreover, as all vertex degrees in Ĥ are at most
0 0
4, |EĤ0 (A , B )| ≤ 4|X| ≤ 8 8mdα.
Note that cut (A0 , B0 ) in graph Ĥ0 naturally defines a cut (A00 , B00 ) in graph Ĥ, where a vertex v ∈
V (Ĥ) is added to A00 if it lies in the set A0 , and it is added to B00 otherwise. It is easy to verify that
|A00 ∩ Π|, |B00 ∩ Π| ≤ 4m/3 still holds. √ Moreover, the number of edges in the cut may only decrease, that
is, |EĤ (A00 , B00 )| ≤ |EĤ0 (A0 , B0 )| ≤ 8 8mdα. For convenience, we will denote the cut (A00 , B00 ) by (A0 , B0 )
from now on, and we will only continue working with this cut.
Unfortunately, the cut (A0 , B0 ) of Ĥ 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 B0 . 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 6.24. 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 , B0 ) if V (Qv ) ∩ A0 and V (Qv ) ∩ B0 6= 0.
/ We say that it
is split evenly iff if |Π(v) ∩ A0 |, |Π(v) ∩ B0 | ≥ dv /8; otherwise we say that it is split unevenly. We modify
the cut (A0 , B0 ) 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 one-by-one.
Consider any such vertex v. If |Π(v) ∩ A0 | > |Π(v) ∩ B0 |, then we move all vertices of Qv to A0 ; otherwise
we move all vertices of Qv to B0 . Assume without loss of generality that the former happens. Notice
that from Observation 6.24, |E(A0 , B0 )| does not increase, since E(Qv ) contributed at least |Π(v) ∩ B0 |
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 45
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
regular edges to the cut before the current iteration. Moreover, |Π(v) ∩ A0 | increases by the factor of at
most 8/7. Therefore, at the end of this procedure, once √ all unevenly split vertices of H are processed,
|A0 ∩ Π|, |B0 ∩ Π| ≤ 78 · 43 m = 32
21 m and |E(A 0 , B0 )| ≤ 8 8mdα.
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 ∩ Π| ≤ |B0 ∩ Π|, then we
move all vertices of Qv to A0 ; otherwise we move them to B0 . Assume without loss of generality that the
former happened. Then before the current iteration |A0 ∩ Π| ≤ |Π|/2 ≤ m, and, since |Π(v)| ≤ d < m/21,
|A0 ∩ Π| ≤ 32 0 32
21 m, while |B ∩ Π| ≤ 21 m as before. Moreover, from Observation 6.24, before the current
iteration, the regular edges of Qv contributed at least d(v)/8 edges to E(A0 , B0 ), 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
0 0
√that are evenly split are processed, |E(A , B )| grows by the
edges to it. Therefore, after all vertices of H
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
|EĤ0 (A , B )| ≤ 64 8mdα. It remains to show that |EH (A∗ )|, |EH (B∗ )| ≥ |E(H)|/32. We show that
|EH (A∗ )| ≥ |E(H)|/32; the proof that |EH (B∗ )| ≥ |E(H)|/32 is symmetric. Observe that ∑v∈B∗ dv =
|B0 ∩ Π| ≤ 32m while ∑v∈V (H) dv = 2m. Therefore, ∑v∈A∗ dv ≥ 2m − 32m
21 , p
10m ∗ ∗
21 = 21 . But |EH (A , B )| ≤
√
64 8mdα ≤ 64 m2 /217 < m/4 (since m > 220 dα). Therefore,
∑v∈A∗ dv − |EH (A∗ , B∗ )| 5m m m
|EH (A∗ )| = ≥ − ≥ .
2 21 8 32
7 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 The-
orem 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`,h be a grid of length ` and height h, where ` > 0 is an even integer, and h > 0. We
denote by Ĝ0 the wall corresponding to Ĝ, as defined in Section 2. We prove the following analogue of
Theorem 4.3.
Theorem 7.1. There is a constant c∗ > 0, and there is an algorithm, that, given a valid and a (d, d 0 , b)-
regular instance I = (G̃, U1 , U2 , h, r) of (r,h)-GPwB, for some d, d 0 , b > 0, with |V (G̃)| = N and |E(G̃)| =
M, in time poly(NM) constructs an instance Î0 = (Ĝ0 , M) of NDP-Wall with |V (Ĝ0 )| = O(M 4 log2 M),
such that the following hold:
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 46
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
• if I has a perfect solution (of value β ∗ = β ∗ (I)), then instance Î0 has a solution P0 that routes at
β∗
least c∗ log 2
M
demand pairs via node-disjoint paths; and
• there is an algorithm with running time poly(NM), that, given a solution P∗ to the NDP-Wall
|P∗ |
problem instance Î0 , constructs a solution to the (r,h)-GPwB instance I, of value at least c∗ ·log 3
M
.
Notice that plugging Theorem 7.1 into the hardness-of-approximation proof instead of Theorem 4.3, we
extend the hardness result to the NDP problem on wall graphs and complete the proof of Theorem 1.1.
Proof of Theorem 7.1. Let Î = (Ĝ, M) be the instance of NDP-Grid constructed in Theorem 4.3. In
order to obtain an instance Î0 of NDP-Wall, we replace the grid Ĝ with the corresponding wall Ĝ0 as
described above; the set of the demand pairs remains unchanged. We now prove the two assertions about
the resulting instance Î0 , starting from the second one.
Suppose we are given a solution P∗ to the NDP-Wall problem instance Î0 . Since Ĝ0 ⊆ Ĝ, and the set of
demand pairs in instances Î and Î0 is the same, P∗ is also a feasible solution to the NDP-Grid problem
instance Î, and so we can use the efficient algorithm from Theorem 4.3 to construct a solution to the
|P∗ |
(r,h)-GPwB instance I, of value at least c∗ ·log3
M
.
It now remains to prove the first assertion. Assume that I has a perfect solution. From Theorem 4.3,
β∗
instance Î of NDP-Grid has a solution P that routes at least c∗ log 2
M
demand pairs via paths that are
β ∗
spaced-out. It is now enough to show that there is a solution of value c∗ log2
M
to the corresponding instance
Î0 of NDP-Wall.
Consider the spaced-out set P of paths in Ĝ. Recall that for every pair P, P0 of paths, d(V (P),V (P0 )) ≥ 2,
and all paths in P are internally disjoint from the boundaries of the grid Ĝ. For each path P ∈ P,
we will slightly modify P to obtain a new path P0 contained in the wall Ĝ0 , so that the resulting set
P0 = {P0 | P ∈ P} of paths is node-disjoint.
For all 1 ≤ i < `, 1 ≤ j ≤ `, let eij denote the ith edge from the top lying in column W j of the grid Ĝ, so
that eij = (v(i, j), v(i + 1, j)). Let E ∗ = E(Ĝ) \ E(Ĝ0 ) be the set of edges that were deleted from the grid
Ĝ when constructing the wall Ĝ0 . We call the edges of E ∗ bad edges. Notice that only vertical edges
may be bad, and, if eij ∈ E(W j ) is a bad edge, for 1 < j < `, then eij+1 is a good edge. Consider some
bad edge eij = (v(i, j), v(i + 1, j)), such that 1 < j < `, so eij does not lie on the boundary of Ĝ. Let Qij be
the path (v(i, j), v(i, j + 1), v(i + 1, j + 1), v(i + 1, j)). Clearly, path Qij is contained in the wall Ĝ0 . For
every path P ∈ P, we obtain the new path P0 by replacing every bad edge eij ∈ P with the corresponding
path Qij . It is easy to verify that P0 is a path with the same endpoints as P, and that it is contained in the
wall Ĝ0 . Moreover, since the paths in P are spaced-out, the paths in the resulting set P0 = {P0 | P ∈ P}
are node-disjoint.
This completes the proof of Theorem 1.1. In order to prove Theorem 1.2, we show an approximation-
preserving reduction from NDP-Wall to EDP-Wall.
Claim 7.2. Let I = (G, M) be an instance of NDP-Wall, and let I0 be the instance of EDP-Wall consisting
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 47
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
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 I0 , respectively. Then OPT0 ≥ OPT, and there is an efficient algorithm, that, given any
solution P0 to instance I0 of EDP-Wall, computes a solution P to instance I of NDP-Wall of value Ω(|P0 |).
Notice that, from Claim 7.2, 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). Therefore, the proof of Claim 7.2 will complete the
proof of Theorem 1.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 P0 of edge-disjoint paths in G. We show an efficient algorithm to
compute a subset P ⊆ P0 of Ω(|P0 |) paths that are node-disjoint. Since the maximum vertex degree in G
is 3, the only way for two paths P, P0 ∈ P0 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 (P0 ), then we say that P has a conflict with P0 .
We construct a directed graph H, whose vertex set is {vP | P ∈ P0 }, and there is an edge (vP , vP0 ) iff P has
a conflict with P0 . 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
subgraph H 0 ⊆ H of H contains a vertex of total degree at most 8. We construct a set U of vertices of
H, such that no two vertices of U are connected by an edge, using a standard greedy algorithm: while
H 6= 0,
/ select a vertex v ∈ 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)|) = Ω(|P0 |), 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| = Ω(|P0 |).
Appendix
A Proof of Theorem 2.6
Suppose G is a Y ES -I NSTANCE, 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 e j = (v j , u j ). Assume that b j = z, for some 1 ≤ z ≤ 6. We assign to v j the color χz (v j ), and
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 48
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
we assign to u j the color χz (u j ). 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 b j = z, for some 1 ≤ z ≤ 6. We assign to v j the color χz (v j ). 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 χb j 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 ≤ `, e j = (v j , u j ). Let c j , c0j are the assignments to v j and u j given by
the jth coordinate of A, so that c j 6= c0j . Recall that there is exactly one index z j ∈ {1, . . . , 6}, such that
χz j assigns the color c j to v j and the color c0j to u j . Let b∗ ∈ B be the vector, where for 1 ≤ j ≤ `, b∗j = z j .
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 c j . Recall that there are
exactly two indices z ∈ {1, . . . , 6}, such that χz assigns the color c j to v j . Denote this set of two indices
by Z j ⊆ {1, . . . , 6}. Consider now some vector b ∈ B. If, for all 1 ≤ j ≤ `, b j ∈ Z j , then fb (Q0 ) = A0 ;
otherwise, fb (Q0 ) 6= A0 . Therefore, the total number of vectors b ∈ B, for which fb (Q0 ) = A0 is exactly 2` .
B Proof of Observation 6.4
We use the standard greedy algorithm. Start with S0 = 0, / and then iterate. In each iteration i, we consider
the current partial solution S0 , and let Ji be the set of all elements j, such that j 6∈ S∈S0 S. We let Si ∈ S
S
be the set containing largest number of elements in Ji , add Si to S0 , and continue to the next iteration. The
algorithm terminates once Ji = 0. /
In order to analyze the algorithm, consider the ith iteration. Notice that, since every element belongs
to at least m/t sets of S, there must be at least one set S ∈ S that contains at least |Ji |/t elements of Ji .
Therefore, set Si that the algorithm chooses covers at least |Ji |/t elements of Ji , and |Ji+1 | ≤ (1 − 1/t)|Ji |.
Overall, we get that for all i, |Ji | ≤ (1 − 1/t)i−1 n, and so both |S0 |, and the number of iterations are
bounded by O(t log n).
C Proof of Claim 6.13
The goal of this section is to prove Claim 6.13. We show an efficient algorithm to construct a set
P1 = {P1 , . . . , PM0 } 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 W j , and that Pi contains the vertex xi .
Fix some index 1 ≤ j ≤ N1 , and consider the box K̂ j . Let I 0j and I 00j denote the top and the bottom
boundaries of K̂ j , respectively. For each 1 ≤ i ≤ M 0 , let W ji denote the ith column of W j , and let x0 ( j, i)
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 49
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
and x00 ( j, i) denote the topmost and the bottommost vertices of W ji , respectively.
For convenience, for each 1 ≤ i ≤ M 0 we denote x00 (0, i) = xi , and we let I000 ⊆ R be a subpath of R
containing exactly 2M vertices, such that x1 , . . . , xM0 ∈ I000 . The following claim is central to the proof.
n 0
o
Claim C.1. There is an efficient algorithm to construct, for each 1 ≤ j ≤ N1 , a set P j = 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);
j=1 P j of paths is spaced-out; and
SN1
• the set
j=1 P j are contained in G , and are internally disjoint from R.
SN1 t
• all paths in
Notice that by combining the paths in Nj=1 P j with the set Nj=1 W j of columns of the boxes, we obtain
1
S 1
S
the desired set P of paths, completing the proof of Claim 6.13. In the remainder of this section we focus
1
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 Ĝ. It is also separated by at least 4M rows from the top boundary of Ĝ 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 Ĝ and a set W of consecutive columns of Ĝ, we denote by ϒ(L, W)
the subgraph of Ĝ spanned by the rows in L and the columns in W; we refer to such a graph as a 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 if every vertex v ∈ ϒ ∩ ϒ0 belongs to the boundaries of both corridors. We say that
two internally disjoint corridors ϒ, ϒ0 are neighbors if ϒ ∩ ϒ0 6= 0.
/ 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 ≤ z0 , z00 ≤ z, the corridor ϒz0 is a neighbor of ϒz00 iff |z0 − z00 | = 1. The width of the snake
is defined to be the minimum of two quantities: (i) min1≤z0 <z {|ϒz0 ∩ ϒz0 +1 |}; and (ii) min1≤z0 ≤z {w(ϒz0 )}.
Notice that, given a snake Y, there is a unique simple cycle σ (Y) contained in zz0 =1 ϒz0 , such that, if D
S
Sz
denotes the disc on the plane whose boundary is σ (Y), then every vertex of z0 =1 ϒz0 lies in D, while
every other vertex of Ĝ lies outside D. We call σ (Y) the boundary of Y. We say that a vertex u belongs to
a snake Y, and denote u ∈ Y, if u ∈ zz0 =1 ϒz0 . We use the following simple claim, whose proof can be
S
found, e. g., in [19].
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 .
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 50
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
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 B0 ⊆ L0 . We say that the paths in Q are order-preserving if 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 B0 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 B0 lie
on the top boundary edge of ϒz and for every pair v, v0 ∈ B ∪ B0 of vertices, dĜ (v, v0 ) ≥ 2. There is an
efficient algorithm, that, given the snake Y, and the sets B and B0 of vertices as above, computes a set Q̂
of spaced-out order-preserving paths contained in Y.
Proof. Let B = {b1 , b2 , . . . , br } and B0 = {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 vertex set A = {a1 , . . . , a2r−1 }, such
that for all 1 ≤ i ≤ r, a2i−1 = bi , and the vertices of A are indexed according to their left-to-right ordering
0 0
0 0
on the bottom boundary of ϒ1 . Similarly, we can augment the set B to a set A = a1 , . . . , a2r−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 subgraphs:
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.
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 subgraphs, 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 Y j of
width at least 2M in Gt , such that all resulting snakes are mutually disjoint, and for each 1 ≤ j ≤ N1 :
• the bottom boundary of the first corridor of Y j contains I 00j−1 ;
• the top boundary of the last corridor of Y j contains I 0j ; 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.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 51
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
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 P j of spaced-
out paths contained in Y j , such that for each 1 ≤ i ≤ M 0 , there is a path Pji ∈ P j connecting vertex
x00 ( j − 1, i) to vertex x0 ( j, i). For each 1 ≤ i ≤ M 0 , let Pi be the path obtained by concatenating the paths
P1i , Wi1 , P2i , . . . , PNi 1 , WiN1 . The final set of paths is P1 = {P1 , . . . , PM0 }.
D Acknowledgment
We thank the anonymous reviewers for carefully reading this manuscript and for their many helpful
suggestions on simplifying and improving the presentation, especially for the suggestion on how to
derandomize the original randomized reduction.
References
[1] N OGA A LON , S ANJEEV A RORA , R AJSEKAR M ANOKARAN , DANA M OSHKOVITZ , AND O MRI
W EINSTEIN: Inapproximabilty of densest k-subgraph from average case hardness, 2011. Manuscript.
6
[2] N OGA A LON , PAUL S EYMOUR , AND ROBIN T HOMAS: Planar separators. SIAM J. Discr. Math.,
7(2):184–193, 1994. [doi:10.1137/S0895480191198768] 44
[3] M ATTHEW A NDREWS: Approximation algorithms for the edge-disjoint paths problem via
Raecke decompositions. In Proc. 51st FOCS, pp. 277–286. IEEE Comp. Soc., 2010.
[doi:10.1109/FOCS.2010.33] 5
[4] M ATTHEW A NDREWS , J ULIA C HUZHOY, V ENKATESAN G URUSWAMI , S ANJEEV K HANNA ,
K UNAL TALWAR , AND L ISA Z HANG: Inapproximability of edge-disjoint paths and low congestion
routing on undirected graphs. Combinatorica, 30(5):485–520, 2010. [doi:10.1007/s00493-010-
2455-9] 3, 5
[5] M ATTHEW A NDREWS AND L ISA Z HANG: Logarithmic hardness of the undirected edge-disjoint
paths problem. J. ACM, 53(5):745–761, 2006. [doi:10.1145/1183907.1183910] 3
[6] YONATAN AUMANN AND Y UVAL R ABANI: Improved bounds for all optical routing. In Proc. 6th
Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’95), pp. 567–576. SIAM, 1995. ACM DL.
4, 5
[7] BARUCH AWERBUCH , R AINER G AWLICK , T OM L EIGHTON , AND Y UVAL R ABANI: On-line
admission control and circuit routing for high performance computing and communication. In Proc.
35th FOCS, pp. 412–423. IEEE Comp. Soc., 1994. [doi:10.1109/SFCS.1994.365675] 5
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 52
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
[8] A DITYA B HASKARA , M OSES C HARIKAR , E DEN C HLAMTAC , U RIEL F EIGE , AND A RAVINDAN
V IJAYARAGHAVAN: Detecting high log-densities: an O(n1/4 ) approximation for densest k-subgraph.
In Proc. 42nd STOC, pp. 201–210. ACM Press, 2010. [doi:10.1145/1806689.1806719] 6
[9] A NDREI Z. B RODER , A LAN M. F RIEZE , S TEPHEN S UEN , AND E LI U PFAL: Optimal con-
struction of edge-disjoint paths in random graphs. SIAM J. Comput., 28(2):541–573, 1998.
[doi:10.1137/S0097539795290805] 5
[10] A NDREI Z. B RODER , A LAN M. F RIEZE , AND E LI U PFAL: Existence and construction of edge
disjoint paths on expander graphs. SIAM J. Comput., 23(5):976–989, 1994. Preliminary version in
STOC’92. [doi:10.1137/S0097539792232021] 5
[11] C HANDRA C HEKURI AND A LINA E NE: Poly-logarithmic approximation for maximum node
disjoint paths with constant congestion. In Proc. 24th Ann. ACM-SIAM Symp. on Discrete Algorithms
(SODA’13), pp. 326–341. SIAM, 2013. [doi:10.1137/1.9781611973105.24] 5
[12] C HANDRA C HEKURI , S ANJEEV K HANNA , AND F. B RUCE S HEPHERD: Multicommodity flow,
well-linked terminals, and routing problems. In Proc. 37th STOC, pp. 183–192. ACM Press, 2005.
[doi:10.1145/1060590.1060618] 5
√
[13] C HANDRA C HEKURI , S ANJEEV K HANNA , AND F. B RUCE S HEPHERD: An O( n) approximation
and integrality gap for disjoint paths and unsplittable flow. Theory of Computing, 2(7):137–146,
2006. [doi:10.4086/toc.2006.v002a007] 4
[14] C HANDRA C HEKURI , S ANJEEV K HANNA , AND F. B RUCE S HEPHERD: Edge-disjoint paths in
planar graphs with constant congestion. SIAM J. Comput., 39(1):281–301, 2009. Preliminary
version in STOC’06. [doi:10.1137/060674442] 5
[15] C HANDRA C HEKURI , M ARCELO M YDLARZ , AND F. B RUCE S HEPHERD: Multicommodity
demand flow in a tree and packing integer programs. ACM Trans. Algorithms, 3(3):27:1–27:23,
2007. [doi:10.1145/1273340.1273343] 5
[16] J ULIA C HUZHOY: Routing in undirected graphs with constant congestion. SIAM J. Comput.,
45(4):1490–1532, 2016. [doi:10.1137/130910464] 5
[17] J ULIA C HUZHOY AND DAVID H ONG K YUN K IM: On approximating node-disjoint paths in
grids. In Proc. 18th Internat. Workshop on Approximation Algorithms for Combinat. Opt.
Probl. (APPROX’15), pp. 187–211. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015.
[doi:10.4230/LIPIcs.APPROX-RANDOM.2015.187] 3, 4
[18] J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND S HI L I: Improved approximation for
node-disjoint paths in planar graphs. In Proc. 48th STOC, pp. 556–569. ACM Press, 2016.
[doi:10.1145/2897518.2897538] 3
[19] J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT: New hardness re-
sults for routing on disjoint paths. In Proc. 49th STOC, pp. 86–99. ACM Press, 2017.
[doi:10.1145/3055399.3055411] 3, 4, 7, 50
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 53
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
[20] J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT: Almost polynomial
hardness of node-disjoint paths in grids. In Proc. 50th STOC, pp. 1220–1233. ACM Press, 2018.
[doi:10.1145/3188745.3188772] 1
[21] J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT: Improved approximation
for node-disjoint paths in grids with sources on the boundary. In Proc. 45th Internat. Colloq. on
Automata, Languages, and Programming (ICALP’18), pp. 38:1–38:14. Schloss Dagstuhl–Leibniz-
Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.ICALP.2018.38] 4
[22] J ULIA C HUZHOY AND S HI L I: A polylogarithmic approximation algorithm for edge-disjoint
paths with congestion 2. J. ACM, 63(5):45:1–45:51, 2016. Preliminary version in FOCS’12.
[doi:10.1145/2893472] 5
[23] S HIMON E VEN , A LON I TAI , AND A DI S HAMIR: On the complexity of timetable and multicom-
modity flow problems. SIAM J. Comput., 5(4):691–703, 1976. [doi:10.1137/0205048] 3
[24] U RIEL F EIGE: Relations between average case complexity and approximation complexity. In Proc.
34th STOC, pp. 534–543. ACM Press, 2002. [doi:10.1145/509907.509985] 6
[25] U RIEL F EIGE , M AGNÚS M. H ALLDÓRSSON , G UY KORTSARZ , AND A RAVIND S RINI -
VASAN : Approximating the domatic number. SIAM J. Comput., 32(1):172–195, 2002.
[doi:10.1137/S0097539700380754] 9
[26] K RZYSZTOF F LESZAR , M ATTHIAS M NICH , AND J OACHIM S POERHASE: New algorithms for max-
imum disjoint paths based on tree-likeness. Math. Programming, 171:433–461, 2018. Preliminary
version in ESA’16. [doi:10.1007/s10107-017-1199-3] 5
[27] A LAN M. F RIEZE: Edge-disjoint paths in expander graphs. SIAM J. Comput., 30(6):1790–1801,
2001. Preliminary version in SODA’00. [doi:10.1137/S0097539700366103] 5
[28] NAVEEN G ARG , V IJAY V. VAZIRANI , AND M IHALIS YANNAKAKIS: Primal-dual approxi-
mation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3–20, 1997.
[doi:10.1007/BF02523685] 5
[29] T HOMAS H OLENSTEIN: Parallel repetition: Simplification and the no-signaling
case. Theory of Computing, 5(8):141–172, 2009. Preliminary version in STOC’07.
[doi:10.4086/toc.2009.v005a008] 11
[30] R ICHARD K ARP: On the complexity of combinatorial problems. Networks, 5(1):45–68, 1975.
[doi:10.1002/net.1975.5.1.45] 3
[31] K EN -I CHI K AWARABAYASHI AND Y USUKE 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, 2013. [doi:10.1145/2438645.2438648] 5
[32] S UBHASH K HOT: Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique.
SIAM J. Comput., 36(4):1025–1071, 2006. [doi:10.1137/S0097539705447037] 6
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 54
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
[33] J ON K LEINBERG: An approximation algorithm for the disjoint paths problem in even-degree planar
graphs. In Proc. 46th FOCS, pp. 627–636. IEEE Comp. Soc., 2005. [doi:10.1109/SFCS.2005.18] 5
[34] J ON K LEINBERG AND RONITT RUBINFELD: Short paths in expander graphs. In Proc. 37th FOCS,
pp. 86–95. IEEE Comp. Soc., 1996. [doi:10.1109/SFCS.1996.548467] 5
[35] J ON M. K LEINBERG AND É VA TARDOS: Disjoint paths in densely embedded graphs. In Proc.
36th FOCS, pp. 52–61. IEEE Comp. Soc., 1995. [doi:10.1109/SFCS.1995.492462] 4, 5
[36] J ON M. K LEINBERG AND É VA TARDOS: Approximations for the disjoint paths problem in high-
diameter planar networks. J. Comput. System Sci., 57(1):61–73, 1998. [doi:10.1006/jcss.1998.1579]
4, 5
[37] S TAVROS G. KOLLIOPOULOS AND C LIFFORD S TEIN: Approximating disjoint-path problems
using packing integer programs. Math. Programming, 99(1):63–87, 2004. [doi:10.1007/s10107-
002-0370-6] 3, 4
[38] M ARK R. K RAMER AND JAN VAN L EEUWEN: The complexity of wire-routing and finding
minimum area layouts for arbitrary VLSI circuits. Adv. Comput. Res., 2:129–146, 1984. 3
[39] T OM L EIGHTON AND S ATISH R AO: Multicommodity max-flow min-cut theorems and their use in
designing approximation algorithms. J. ACM, 46(6):787–832, 1999. [doi:10.1145/331524.331526]
5
[40] R ICHARD J. L IPTON AND ROBERT E NDRE TARJAN: A separator theorem for planar graphs. SIAM
J. Appl. Math., 36(2):177–189, 1979. [doi:10.1137/0136016] 44, 45
[41] JAMES F. LYNCH: The equivalence of theorem proving and the interconnection problem. SIGDA
Newsl., 5(3):31–36, 1975. [doi:10.1145/1061425.1061430] 3
[42] PASIN M ANURANGSI: Almost-polynomial ratio ETH-hardness of approximating densest k-
subgraph. In Proc. 49th STOC, pp. 954–961. ACM Press, 2017. [doi:10.1145/3055399.3055412]
6
[43] H ARALD R ÄCKE: Minimizing congestion in general networks. In Proc. 43rd FOCS, pp. 43–52.
IEEE Comp. Soc., 2002. [doi:10.1109/SFCS.2002.1181881] 5
[44] P RABHAKAR R AGHAVAN AND C LARK D. T HOMPSON: Randomized rounding: a technique
for provably good algorithms and algorithmic proofs. Combinatorica, 7(4):365–374, 1987.
[doi:10.1007/BF02579324] 5
[45] P RASAD R AGHAVENDRA AND DAVID S TEURER: Graph expansion and the unique games con-
jecture. In Proc. 42nd STOC, pp. 755–764. ACM Press, 2010. [doi:10.1145/1806689.1806792]
6
[46] A NUP R AO: Parallel repetition in projection games and a concentration bound. SIAM J. Comput.,
40(6):1871–1891, 2011. Preliminary version in STOC’08. [doi:10.1137/080734042] 11
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 55
J ULIA C HUZHOY, DAVID H ONG K YUN K IM , AND R ACHIT N IMAVAT
[47] S ATISH R AO AND S HUHENG Z HOU: Edge disjoint paths in moderately connected graphs. SIAM J.
Comput., 39(5):1856–1887, 2010. [doi:10.1137/080715093] 5
[48] R AN R AZ: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998.
[doi:10.1137/S0097539795280895] 11
[49] N EIL ROBERTSON AND PAUL D. S EYMOUR: Outline of a disjoint paths algorithm. In Paths, Flows
and VLSI-Layout. Springer, 1990. WorldCat.org. 3
[50] N EIL ROBERTSON AND PAUL D. S EYMOUR: Graph minors. XIII. The disjoint paths problem. J.
Combin. Theory–B, 63(1):65–110, 1995. [doi:10.1006/jctb.1995.1006] 3
[51] L OÏC S ÉGUIN -C HARBONNEAU AND F. B RUCE S HEPHERD: Maximum edge-disjoint paths in
planar graphs with congestion 2. Math. Programming, 188:295–317, 2021. Preliminary version in
FOCS’11. [doi:10.1007/s10107-020-01513-1] 5
[52] P ETER U NGAR: A theorem on planar graphs. J. London Math. Soc., 26(4):256–262, 1951.
[doi:10.1112/jlms/s1-26.4.256] 44
AUTHORS
Julia Chuzhoy
Professor
Toyota Technological Institute at Chicago
Chicago, IL, USA
cjulia ttic edu
https://ttic.uchicago.edu/~cjulia
David Hong Kyun Kim
Software Engineer
Google
Sunnyvale, CA, USA
dave hongk gmail.com
http://people.cs.uchicago.edu/~hongk
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 56
A LMOST P OLYNOMIAL H ARDNESS OF N ODE -D ISJOINT PATHS IN G RIDS
Rachit Nimavat
Ph. D. Student
Toyota Technological Institute at Chicago
Chicago, IL, USA
nimavat ttic edu
https://home.ttic.edu/~nimavat
ABOUT THE AUTHORS
J ULIA C HUZHOY is a Professor at the Toyota Technological Institute at Chicago. She
completed her Ph. D. at the Technion, Israel, and spent three years as a postdoctoral
scholar at MIT, the University of Pennsylvania and the Institute for Advanced Study in
Princeton. She mainly works on algorithms for graph problems. In her spare time she
likes to read books, learns to play piano and studies French.
DAVID H ONG K YUN K IM received his Ph. D. in Computer Science in May 2018 from
the University of Chicago, where he studied approximation algorithms for network
routing problems under the supervision of Julia Chuzhoy. He also worked on scheduling
problems and their applications to real systems with Henry Hoffmann. He now works as
a software engineer at Google and enjoys spending his free time hiking and listening to
music.
R ACHIT N IMAVAT is a Ph. D. student at the Toyota Technological Institute, Chicago (TTIC).
His advisor is Julia Chuzhoy. In 2015, Rachit received his BTech in Computer Science
and Engineering from the Indian Institute of Technology, Kanpur, under the supervision
of Prof. Surender Baswana. Rachit’s work is mainly in approximation algorithms and
hardness of approximation. In his free time he likes to cook, while trying to optimize the
ratio of taste over effort. His favorite cuisine is of his home state of Gujarat, India.
T HEORY OF C OMPUTING, Volume 17 (6), 2021, pp. 1–57 57