Graph Theory and Its Uses in Graph Algorithms and Beyond

Rachit Nimavat

A thesis submitted
in partial fulfillment of the requirements for
the degree of
Doctor of Philosophy in Computer Science
at the

TOYOTA TECHNOLOGICAL INSTITUTE AT CHICAGO
Chicago, Illinois

August 2023

Thesis Committee:
Julia Chuzhoy (Thesis Advisor)
Sanjeev Khanna
Yury Makarychev

###### Abstract

Graphs are fundamental objects that find widespread applications across
computer science and beyond. Graph Theory has yielded deep insights about
structural properties of various families of graphs, which have been leveraged
in the design and analysis of algorithms for graph optimization problems and
other computational optimization problems. These insights have also proved
especially helpful in understanding the limits of efficient computation by
providing constructions of hard problem instances. At the same time,
algorithmic tools and techniques provide a fresh perspective on graph
theoretic problems, often leading to novel discoveries. In this thesis, we
exploit this symbiotic relationship between graph theory and algorithms for
graph optimization problems and beyond. This thesis consists of three parts.

In the first part, we study a classical graph routing problem called the Node-
Disjoint Paths (NDP) problem. Given an undirected graph and a set of source-
destination pairs of its vertices, the goal in this problem is to route the
maximum number of pairs via node-disjoint paths. We come close to resolving
the approximability of NDP by showing that NDP is
$n^{\Omega(1/\operatorname{poly}\log\log n)}$-hard to approximate, even on
grid graphs, where $n$ is the number of grid vertices. In the second part of
this thesis, we use graph decomposition techniques developed for efficient
algorithms and tools from the analysis of random processes to derive a graph
theoretic result. Specifically, we show that for every $n$-vertex expander
graph $G$, if $H$ is any graph containing at most $O(n/\log n)$ vertices and
edges, then $H$ is a minor of $G$. We also present an algorithm that, given a
target graph computes its model in the input host graph. These two parts
highlight the intimate relationship between graph theory and graph algorithms.

In the last part of this thesis, we show that the graph theoretic tools and
graph algorithmic techniques can shed light on problems seemingly unrelated to
graphs. Specifically, we demonstrate that the randomized space complexity of
the Longest Increasing Subsequence (LIS) problem in the streaming model is
intrinsically tied to the query-complexity of the Non-Crossing Matching
problem on graphs in a new model of computation that we define. Leveraging the
insights obtained from this connection, we also design a better randomized
algorithm for the LIS problem in the streaming model.

### Acknowledgements

I would like to start by expressing my gratitude to my advisor Julia Chuzhoy
for her immense patience, guidance, support, and unwavering belief in me. She
graciously explained research ideas, taught me techniques, and meticulously
reviewed my writing to bring it (a bit) closer to her standards. I am forever
grateful for her generosity with her time and insights about both: research
and life. Thank you, Julia, for the delicious flourless chocolate cakes and
for introducing me to the joy of snacking on coffee beans! I am thankful to
Sanjeev Khanna for his valuable advice, and am grateful that I got a chance to
learn from him. His humility and wisdom continue to inspire me. I would also
like to thank Yury Makarychev for being a part of my thesis committee and for
his encouragement and support. I am thankful to Madhur Tulsiani for his time,
support, understanding, and for being a constant source of inspiration. I am
also thankful to my co-authors and collaborators Sanjeev Khanna and David Kim.
It was a pleasure to discuss ideas and work with them.

From the bottom of my heart, I am grateful to TTIC for providing a friendly
and vibrant environment for students. With an abundance of talks and food,
student outings, and close interactions with professors, visitors, and fellow
students, TTIC has been the highlight of my experience and my home in the US.
A huge thanks to the admin staff, especially Amy and Chrissy, for making
everything happen seamlessly. I am also eternally grateful to Mary for her
kindness and pampering of students, treating us like her own children. Many
thanks to friends at TTIC and UChicago for making my time here fun and
interesting: Anmol, Behnam, Chris, David, Diego, Fernando, Goutham, Hao,
Jerry, Kshitij, Marziyeh, Naren, Omar, Riddhima, Robby, Shane, Srinadh,
Subhasmita, Suriya, Willie, Yuval, Zihan. Shubham, my first roommate in
Chicago, made my life here so much more happening with his moral support,
quick wit, and (mis)adventures. Haris and Mrinal were the other theory
students at TTIC when I joined, and I thank them both for patiently answering
my questions without making me feel stupid. A warm thank you to Somaye for
showing me the secret access to the rooftop - I’ve lost count of the number of
rainbows, snowfights, and sunsets I’ve enjoyed there. I had a great time
bantering with office-mates Pedro and Qingming - thank you for watching my
back whenever I took naps. I thank Akash and Shubhendu for their semi-
permanent presence at TTIC and lake respectively. Thank you Ankita for
delicious food and sharing my frustration of not understanding how seasons
work. Special thanks to Pushkar and Sudarshan for fighting with their landlady
and allowing me to stay at their place. I had many ‘insightful’ discussions
with Shashank while exploring Chicago. Thank you for putting up with me and
laughing at my jokes when no one else would. I hope to convince you for a late
night Red Line ride someday.

When I arrived in Chicago, I was unsure what to expect. I am thankful to Raut
uncle and his family for easing my transition. As I began to explore the city,
I found myself pleasantly surprised by its charm and warmth. Like taking a
plunge into the cool waters of Lake Michigan, once you get past the initial
shock, you’ll find that the city is surprisingly open and embraces you with
open arms. With its rich history and diverse population, Chicago offered me
the opportunity to interact with people from all walks of life. As I immersed
myself in its vibrant culture, I realized that Chicago is a place that I could
be proud to be a part of.

I thank my cousin Pinakin for choosing to come to Chicago for his studies and
for always cheering me up. Huge thanks to my friends Bhagwat and Lokesh for
frequently stopping by, checking on me, and taking me on long road-trips. I
have had the pleasure of going on memorable trips with Arnab, Deep, Dharmil,
Divya, Eeshit, Naman, Pinakin, Rohit, Shubham, Yajat, and Yuval. These trips
were filled with laughter and adventure and allowed me to discover the vast
and picturesque landscapes of the US, which I fell in love with. Along the
way, I met many kind-hearted strangers who helped me on countless occasions.
Their warmth and generosity never cease to amaze me.

My gratitude goes out to all my friends from IIT Kanpur, especially those from
my wing and department, who made me feel right at home. I am deeply grateful
to Prof. Surender Baswana, without whom I would never have considered grad
school. It is an honor to be his student. During my school years, Ankur Sir
and Deepak Sir sparked my curiosity in maths, that I hope will stay with me
for a lifetime. A special thanks to Aakash and Samarth for sharing soda with
me whenever we meet. Even though it may have been months since we last spoke,
talking with them feels as if we had just met yesterday.

I cannot express enough gratitude to my parents, Anil and Arti, for their
unconditional support and trust. From early childhood, they have given me the
freedom to explore and learn, always encouraging me with no questions asked.
You have always found happiness in my happiness. I am forever grateful for
your love. I am also grateful to my masi, Asha, for her love and encouragement
since as far back as I can remember. You are a second mother to me. To Divya,
I am deeply grateful for your understanding, encouragement, and love. I admire
your curiosity and perseverance and I hope to emulate your kindness, even if
it is only a constant factor approximation. I would like to thank my late
grandparents, my extended family in Gujarat, and my neighbors in Bhavnagar.
Their cheers and encouragement have always lifted my spirits, and I feel
privileged to have received their love.

I consider myself extremely fortunate to be surrounded by amazing people in
life: family, friends, neighbors, classmates, teachers, and all other fellow
life-travelers. Thank you all for being there for me. Your love and support
mean the world to me.

###### Contents

  1. 1 Introduction
    1. 1.1 Node-Disjoint Paths
    2. 1.2 Large Minors in Expanders
    3. 1.3 Longest Increasing Subsequence and Non-Crossing Matchings
  2. 2 Node-Disjoint Paths
    1. 2.1 Introduction
      1. 2.1.1 Our Results and Informal Overview of Techniques
      2. 2.1.2 Organization
    2. 2.2 Preliminaries
    3. 2.3 The (r,h)-Graph Partitioning Problem with Bundles
      1. 2.3.1 From 3COL(5) to (r,h)-GPwB
      2. 2.3.2 From (r,h)-GPwB to NDP-Grid
    4. 2.4 The Hardness Proof
      1. 2.4.1 Prover Strategy or Partition — Proof of Theorem 2.4.1
    5. 2.5 From (r,h)-Graph Partitioning Problem with Bundles to NDP on Grid Graphs
      1. 2.5.1 The Construction
      2. 2.5.2 From Partitioning to Routing
      3. 2.5.3 From Routing to Partitioning
    6. 2.6 Hardness of NDP and EDP on Wall Graphs
  3. 3 Large Minors in Expanders
    1. 3.1 Introduction
      1. 3.1.1 Our Results and Informal Overview of Techniques
      2. 3.1.2 Organization
    2. 3.2 Preliminaries
    3. 3.3 Expanders Contain all Not-So-Large Graphs as Minors
    4. 3.4 Embedding Target-Graph in a Path-of-Expanders System
      1. 3.4.1 Embedding Almost All Edges of the Target-Graph
      2. 3.4.2 Embedding Remaining Edges of the Target-Graph
    5. 3.5 Large Path-of-Expanders System in Expanders
      1. 3.5.1 Expanding Path-of-Sets System
      2. 3.5.2 From Expanding Path-of-Sets System to Strong Path-of-Sets System
      3. 3.5.3 From Strong Path-of-Sets System to Path-of-Expanders System
    6. 3.6 Efficiently Finding Models of all Not-So-Large Graphs in Expanders
  4. 4 Longest Increasing Subsequence and Non-Crossing Matching
    1. 4.1 Introduction
      1. 4.1.1 Our Results and Informal Overview of Techniques
      2. 4.1.2 Previous Work
      3. 4.1.3 Organization
    2. 4.2 Preliminaries
    3. 4.3 From LIS in Streaming Model to NCM in Hybrid Model
    4. 4.4 Hierarchical Decomposition
      1. 4.4.1 Partition Lemma
      2. 4.4.2 Efficiently Enumerating Ensembles
    5. 4.5 From NCM in Hybrid Model to LIS in Streaming Model
      1. 4.5.1 Special Case $1$ : Stream-blocks are Small
      2. 4.5.2 Special Case 2: Yes-pairs Share Many Common Elements
      3. 4.5.3 LIS Streaming Algorithm with Space Complexity $N^{1/2+O(\epsilon)}$
      4. 4.5.4 Processing the Ensemble
      5. 4.5.5 Special Case 3: Jumpable Tuples have Large Level-Weight
      6. 4.5.6 ${\mathsf{Alg}}\mathsf{Jump}{(i)}$ and its Properties — Proof of Lemma 4.5.29
      7. 4.5.7 $\mathsf{Alg}{\mathsf{Gen}}$ and its Properties — Proof of Lemma 4.5.35
      8. 4.5.8 Special Case 4: Savable Levels have Large Weight
      9. 4.5.9 $\mathsf{Alg}\mathsf{Savable}{(i)}$ and its Properties — Proof of Lemma 4.5.48
    6. 4.6 Randomized LIS Algorithm in Streaming Model with $\alpha$-approximation
  5. A Proofs Omitted from Chapter 2
    1. A.1 Proof Omitted from Section 2.2
    2. A.2 Proofs Omitted from Section 2.5
      1. A.2.1 Proofs of Auxillary Lemmas 2.5.2 and 2.5.3
      2. A.2.2 Proof of Observation 2.5.7.
      3. A.2.3 Proof of Observation 2.5.8.
      4. A.2.4 Proof of Observation 2.5.10.
      5. A.2.5 Routing via Spaced-out Paths - Proof of Claim 2.5.13
      6. A.2.6 Proof of Observation 2.5.21.
      7. A.2.7 Observation Proof of 2.5.23.
    3. A.3 Proof Omitted from Section 2.6
  6. B Proofs Omitted from Chapter 3
    1. B.1 Proofs Omitted from Sections 3.1.1 and 3.2
      1. B.1.1 Proof of Corollary 3.1.3 .
      2. B.1.2 Proof of Observation 3.1.4.
      3. B.1.3 Proof of Observation 3.2.1.
      4. B.1.4 Proof of Claim 3.2.3.
    2. B.2 Proofs Omitted from Section 3.4
      1. B.2.1 Proof of Observation 3.4.1.
      2. B.2.2 Proof of Claim 3.4.6.
      3. B.2.3 Proof of Claim 3.4.10.
      4. B.2.4 Proof of Claim 3.4.11.
      5. B.2.5 Proof of Lemma 3.4.12.
      6. B.2.6 Proof of Theorem B.2.1.
      7. B.2.7 Proof of Theorem B.2.3
      8. B.2.8 Proof of Lemma B.2.5
      9. B.2.9 Proof of Lemma B.2.6
    3. B.3 Proofs Omitted from Section 3.5
      1. B.3.1 Proof of Claim 3.5.3.
      2. B.3.2 Corollary 3.5.4
      3. B.3.3 Proof of Claim 3.5.6.
      4. B.3.4 Proof of Claim 3.5.9.
      5. B.3.5 Proof of Theorem 3.5.10.
  7. C Proofs Omitted from Chapter 4
    1. C.1 Proofs Omitted from Section 4.4
    2. C.2 Proofs Omitted from Section 4.5
      1. C.2.1 Proof Omitted from Section 4.5.1
      2. C.2.2 Proofs Omitted from Section 4.5.2
      3. C.2.3 Proof Omitted from Section 4.5.3
      4. C.2.4 Proofs Omitted from Section 4.5.4
      5. C.2.5 Proofs Omitted from Sections 4.5.5, 4.5.6, and 4.5.7
      6. C.2.6 Proofs Omitted from Sections 4.5.8 and 4.5.9
    3. C.3 Proofs Omitted from Section 4.6

###### List of Figures

  1. 2.1 A wall graph.
  2. 2.2 An iteration description of the algorithm of Theorem 2.1.1
  3. 2.3 Flowchart for an iteration execution of the algorithm of Theorem 2.1.1
  4. 2.4 Routing in the top grid.
  5. 2.5 Grid $Q_{v}$ obtained from $v$
  6. 3.1 An illustration of the Path-of-Expanders System $\Pi=({\mathcal{S}},{\mathcal{M}},A_{1},B_{6},{\mathcal{T}},{\mathcal{M}}^{\prime})$. For each $1\leq i\leq 6$, the vertices of $A_{i}$, $B_{i}$ and $C_{i}$ are shown in red, blue and green, respectively.
  7. 3.2 Preliminaries
  8. 3.4 A sketch of the partition of $T_{2}$ and $B_{2}$ with $|U|=4$. Vertices of $B_{2}$ and $C_{2}$ are shown in blue and red respectively.
  9. Step 3: Routing remaining edges of $H$ in $G^{\prime}_{\Pi}$.
  10. 3.7 An illustration of the Duo-of-Expanders System.
  11. 3.8 An illustration for the proof of Theorem 3.5.1
  12. 3.9 The contractions of the edges on paths $P$ and $Q_{P}$.
  13. 4.1 Input NCM instance $G=(L,R,E_{\mathsf{advice}},E)$, where, $L$ and $R$ contain $6$ vertices each. Only the edges and advice-edges incident on the vertex $u_{3}$ are shown. The advice-edges incident on $u_{3}$ are $e_{1}(u_{3})=(u_{3},v_{1})$, $e_{2}(u_{3})=(u_{3},v_{3})$, and $e_{3}(u_{3})=(u_{3},v_{6})$; where, $e_{1}(u_{3}),e_{2}(u_{3})\in E$ and $e_{3}(u_{3})\in E_{\mathsf{advice}}\backslash E$.
  14. 4.2 LIS instance $S_{G}$ corresponding to the NCM instance $G$ of Figure 4.1. Only the elements of subsequence $B(u_{3})$ corresponding to the vertex $u_{3}$ are shown. Notice that the subsequences $Z(e_{1}(u_{3}))$ and $Z(e_{2}(u_{3}))$ corresponding to ‘real’ edges $e_{1}(u_{3})$ and $e_{2}(u_{3})$ are increasing; while the sequence $Z(e_{3}(u_{3}))$ corresponding to the edge $e_{3}(u_{3})$ is decreasing.
  15. 4.3 LIS instance $\hat{S}_{G}$ corresponding to the LIS and NCM instances of and . Only the elements of subsequence $B(u_{3})$ corresponding to the vertex $u_{3}$ are shown. We have assumed that the first elements of $Z(e_{1}(u_{3}))$ and $Z(e_{3}(u_{3}))$ are present in the item array of our algorithm while processing the second elements of $Z(e_{1}(u_{3}))$ and $Z(e_{3}(u_{3}))$ respectively; and the first element of $Z(e_{2}(u_{3}))$ is absent in the item array of our algorithm while processing the second element of $Z(e_{2}(u_{3}))$. Notice that the subsequence $Z(e_{1}(u_{3}))$ is increasing; while the sequences $Z(e_{2}(u_{3}))$ and $Z(e_{3}(u_{3}))$ are _not_ increasing.

###### List of Tables

  1. 2.1 Approximation tradeoffs for efficient algorithms for the NDP problem in the general case and some special cases.
  2. 2.2 Approximation tradeoffs for efficient algorithms for the EDP problem in the general case and some special cases.
  3. 3.1 Maximum size of arbitrary graphs as minors in an expander $G$ with $n$ vertices, maximum vertex-degree $d$ and expansion $\alpha$.
  4. 4.1 Space-approximation tradeoffs for the LIS problem in the streaming model.

##  Chapter 1 Introduction

Graphs are fundamental objects that find widespread applications across
computer science and beyond. They are a powerful tool for modeling
relationships between objects, such as web pages, molecules, and cities, among
others. These relationships give rise to rich graph structures that are both
interesting in their own right and have direct real-world applications. The
field of Graph Theory is dedicated to studying structural properties of
various families of graphs. This area has a long-standing symbiotic
relationship with the field of Graph Algorithms, where the focus is on
efficiently solving optimization problems involving graphs.

Graph theory has yielded deep insights that have been leveraged in the design
and analysis of algorithms for graph optimization problems and other
computational optimization problems. Apart from Theoretical Computer Science,
a wide variety of fields, including basic sciences, Machine Learning, Data
Science, Social Science, Operation Research, Medicines and beyond have
benefited from these insights and algorithms. The insights drawn from graph
theory have also proved especially helpful in understanding the limits of
efficient computation by hinting at possible hard problem instances. At the
same time, algorithmic tools and techniques provide a fresh perspective on
graph theoretic problems, often leading to novel discoveries. The quest for
designing better algorithms for the real world problems often point us to
previously undiscovered graph structures and the interplay between various
such structures.

In this thesis, we exploit this intimate relationship between graph theory and
graph algorithms in the context of graph optimization problems and beyond.
This thesis consists of three parts. In the first part, we utilize the tools
developed in both graph theory and graph algorithms to study the hardness of
approximation of the Node-Disjoint Paths problem, one of the fundamental graph
routing problems. Then in the second part of this thesis, we apply techniques
developed for efficient graph algorithms and the analysis of random processes
to derive a graph theoretic result. Specifically, we show that for every
$n$-vertex expander graph $G$, if $H$ is any graph containing at most
$O(n/\log n)$ vertices and edges, then $H$ is a minor of $G$. We also present
an algorithm that computes the model of such large target graphs in the host
graph. The first two parts of this thesis highlight the intimate back-and-
forth relationship between graph theory and graph algorithms. In the last
part, we demonstrate that the complexity of the Longest Increasing Subsequence
problem in the streaming model is intrinsically tied to that of the Non-
Crossing Matching problem on graphs. Leveraging the insights obtained from
this matching problem, we design a novel randomized streaming algorithm for
the Longest Increasing Subsequence problem. This relationship affirms that
right graph theoretic tools and graph algorithmic techniques can shed light on
problems seemingly unrelated to graphs.

In the remainder of this chapter, we briefly introduce the problems explored
in each of the three parts of this thesis in turn. A more detailed
introduction to these problems can be found in the subsequent sections of the
respective chapters.

###  1.1 Node-Disjoint Paths

Graph routing problems are a class of graph optimization problems that
involves finding paths or routes between nodes in a graph. These problems
arise in various applications, including transportation networks,
communication networks, and chip design. In Chapter 2 we study a classical
routing problem called the Node-Disjoint Paths (NDP) problem. The problem
takes as input an undirected graph $G$ with $n$ vertices and a set of $k$ pair
of its vertices, called _source-destination pairs_ or _demand pairs_. The
objective is to find the largest collection of paths, each of which connects a
distinct source vertex to its corresponding destination vertex, such that no
two paths share a common node.

The original motivation for this problem came from its applications in VLSI
design, where layout strategies relied on heuristics for finding node-disjoint
paths solution connecting all demand pairs. This is a classic case of a
fundamental graph routing problem originating in the real world and
subsequently extensively studied in both graph theory and theoretical computer
science communities. Robertson and Seymour [RS90, RS95] explored the problem
in their seminal Graph Minor series, providing an efficient algorithm for NDP
when the number $k$ of the demand pairs is a constant. However, when $k$ is a
part of input, it is a classical NP-Hard problem [Kar75, EIS76]. Consequently,
research focus naturally shifted to designing approximation algorithms:
efficient algorithms that compute approximate solutions, minimizing the
_approximation factor_ , the ratio between the size of the optimal solution
and the size of the solution returned by the algorithm.

The best current approximation factor of $O(\sqrt{n})$ for NDP is achieved by
a simple greedy algorithm [KS04]. Surprisingly, until recently, this was the
state-of-the-art even for the graphs containing seemingly exploitable
structures, such as grid graphs. The holy grail in the field of approximation
algorithms is to achieve a tight understanding of the approximability of a
problem through a two prongs approach: demonstrate an efficient algorithm that
achieves some factor of approximation; and prove that improving this factor
any further is NP-Hard. Until our works, only factor
$\Omega\left(\log^{1/2-\epsilon}{n}\right)$-hardness of approximation, for any
constant $\epsilon>0$, was known for the NDP problem [AZ05, ACG+10]. The
approximability status of NDP thus remained wide open.

The focus then shifted to understanding families of instances with more
structure, both in the underlying graph and the placement of the demand pairs
in it. In the special case where the underlying graph is a grid graph, called
NDP-Grid, one might expect that good approximation algorithms can be designed
for this problem or, at the very least, that the problem should be easy to
understand. On the algorithmic side, Chuzhoy and Kim [CK15] designed an
$\tilde{O}(n^{1/4})$-approximation for NDP-Grid. They also showed that NDP-
Grid is APX-Hard. However, despite many efforts, various approximation
techniques to obtain sub-polynomial approximation factors failed for NDP-Grid
and establishing its approximability remained elusive. A natural question then
arises: is the NDP-Grid problem (and hence, NDP problem) genuinely very hard
to approximate within a reasonable factor of approximation? Is it possible to
achieve better, say sub-polynomial, factor of approximation, at least when the
source and destination vertices of the demand pairs in NDP-Grid obey some
structure? In [CKN17] the NDP problem was shown to be hard to approximate
within a factor of $2^{\Omega(\sqrt{\log n})}$ under the standard complexity
theoretic assumptions, even if the underlying graph is a subgraph of a grid
graph, with all sources placed on the grid boundary. Later, [CKN18b] showed an
efficient algorithm for NDP-Grid achieving roughly the same
$2^{\tilde{O}(\sqrt{\log n})}$ factor of approximation, where the input graph
has $n$ vertices, provided all source-vertices of the demand pairs appear
‘close’ to the grid boundary. Together, these result seem to suggest that sub-
polynomial approximation algorithms may be achievable for NDP-Grid, and we
might also have gotten a handle on the ‘correct’ approximation factor
achievable.

However, in [CKN18a], that we discuss in this thesis (see, Chapter 2 for more
details), we show that this is unlikely to be the case, and come close to
resolving the approximability status of NDP-Grid, and of NDP problem in
general. We show that NDP-Grid is
$2^{\Omega\left(\log^{1-\epsilon}{n}\right)}$-hard to approximate for any
constant $\epsilon>0$ under standard complexity theoretic assumptions and a
factor $n^{\Omega\left(1/(\log\log n)^{2}\right)}$ hardness of approximation
under a stronger complexity theoretic assumption. To establish this hardness
result, we perform a Cook reduction from a known NP-Complete problem 3COL(5),
using a newly defined graph partitioning problem as a proxy. We show that the
NDP-Grid problem is almost as hard as this graph partitioning problem. This is
a Karp reduction exploiting graph theoretic insights of viewing routing in
grids as a form of graph drawing, and that graphs with low crossing numbers
have small balanced separators. In contrast, the reduction between 3COL(5) and
the graph partitioning problem is a Cook reduction that uses the celebrated
technique of parallel repetition of two-prover games.

###  1.2 Large Minors in Expanders

Graph minors have been used to prove many fundamental results in graph theory
and computer science. A graph $H$ is a minor of a host graph $G$ if $H$ can be
obtained by deleting some edges and vertices from $G$ and contracting some of
the remaining edges. Perhaps, the most well known result in the study of graph
minors is Wagner’s theorem [Wag37], that provides a complete characterization
of planar graphs as a family of graphs with _forbidden minors_. The seminal
graph minor theorem by Robertson and Seymour [RS04] proved as a part of their
graph minor series is a natural extension of this result, demonstrating that
any minor-closed family of graphs can be characterized as a family of graphs
with forbidden minors. An important ingredient in this result is the excluded
grid theorem [RS86], that is a fundamental and widely used graph theoretic
result in its own right. Among other things, this theorem plays a crucial role
in their efficient algorithm for the NDP problem when the number of demand
pairs is a constant [RS90, RS95]. Informally, this theorem states that any
graph $G$ that has large _treewidth_ (which is a measure of how far is the
graph from being tree-like) contains a grid graph of size dependent on this
treewidth, as a minor. In a long line of works [RS86, RST94, KK12, LS15,
CC16b, Chu15, Chu16a, CT19], progress has been made in one direction of this
relationship, showing the existence of larger and larger grid minors, as a
function of the treewidth of the host graph. The best current lower bound
[CT19] states that every graph with treewidth $t$ has a grid minor of size at
least $\Omega(t^{1/9}/\operatorname{poly}\log
t)\times\Omega(t^{1/9}/\operatorname{poly}\log t)$. But the other direction of
providing an upper bound on the size of the largest possible grid minor as a
function of the treewidth remains elusive. The family of host graphs achieving
the best known upper bound is _expander graphs_. It is well known that
constant-degree expanders have treewidth $\Theta(n)$ and there exists a family
of expander graphs with girth $\Omega(\log n)$, where $n$ is the number of
vertices in the graph. Robertson et al. [RST94] observe that for this family
of expander graph, the size of the largest grid minors does not exceed
$O(n/\log n)$. They suggest that this bound is tight, that is, every graph
with treewidth $t$ has a grid minor of size $\Omega(t/\log t)$.

Expanders are ubiquitous in discrete mathematics, theoretical computer science
and beyond, arising in a wide variety of fields ranging from computational
complexity to designing robust computer networks (see, [HLW06] for a survey).
A graph $G$ is an $\alpha$-expander, if, for every partition $(A,B)$ of its
vertices into non-empty subsets, the number of edges connecting vertices of
$A$ to vertices of $B$ is at least
$\alpha\cdot\left(\min\left\\{|A|,|B|\right\\}\right)$. We say that $G$ is an
expander, its _expansion_ $\alpha$ is at least a constant. This concept has
been extensively studied in the literature, and there are multiple known
explicit families of expanders with constant vertex-degree (see, for example,
[Alo96]). In this section, we will refer to these bounded vertex-degree
expanders as simply expanders. The seemingly contradictory properties of being
extremely well connected while being sparse make expanders fascinating objects
to study in graph theory, in addition to their algorithmic applications. It is
therefore important to understand the size of the largest grid minor in
expander graphs, as it not only sheds light on the structure of these objects
but also deepens our understanding of the excluded grid theorem.

The problem of finding large minors in expanders was first studied by
Kleinberg and Rubinfield [KR96]. Building on the random walk-based techniques
of Broder et al. [BFU94], they showed that every expander $G$ on $n$ vertices
contains every graph with $O(n/\log^{\kappa}n)$ vertices and edges as a minor.
The exponent $\kappa$ in this result depends on the expansion of $G$ and its
maximum vertex-degree, and could be substantially larger than $1$. In [CN19],
that we discuss in this thesis (see, Chapter 3 for more details), we improve
upon this result by showing that every expander $G$ on $n$ vertices with
expansion $\alpha$ and maximum vertex-degree $d$ contain every other graph
with $O\left(\frac{n}{\log n}\cdot\left(\frac{\alpha}{d}\right)^{c}\right)$
vertices and edges as minor, for some absolute constant $c$. Notably, exponent
of $\log n$ in our bound is $1$ and does not depend on the expansion $\alpha$
or maximum vertex degree of the host graph $G$. As demonstrated by [RST94]
this bound achieves optimal dependence on $n$, since there exist expanders
with $n$ vertices that do not contain grid graphs of size greater than
$O(n/\log n)$ as minors. Our result employs a known combinatorial object
called paths-of-set system and its generalization paths-of-expanders system
that we propose, among others. These objects provide a ‘large enough canvas’
in the host expander graph in which any target graph can be embedded. The
computation of such embedding involves finding a routing of a collection of
carefully chosen demand pairs via internally node-disjoint paths. Our
algorithm for computing such a routing is inspired by the algorithm of Frieze
[Fri01] that efficiently routes a large set of demand pairs in an expander
graph via edge-disjoint paths. We also present an algorithm that finds such a
minor in the host graph with runtime polynomial in $n$, but has super-
polynomial dependency on the expansion and maximum vertex-degree of $G$.
Specifically, the runtime of our algorithm is
$O\left(\operatorname{poly}(n)\cdot 2^{\log^{2}{(d/\alpha)}}\right)$, where
$\alpha$ is the expansion of the host graph and $d$ is its maximum vertex-
degree.

We also show a simpler algorithm whose running time is truly polynomial in the
size of the host graph $G$, but can only find graphs containing fewer than
$O\left(\frac{n}{\log^{2}n}\cdot\frac{\alpha^{3}}{d^{5}}\right)$ vertices and
edges as minors in $G$, where $\alpha$ is the expansion of $G$ and $d$ is its
maximum vertex-degree. Unlike the previous result, it does not employ paths-
of-expanders system that inflates the running time of the algorithm as well as
the dependence on $\alpha$ and $d$ in the guaranteed minor size. Instead, we
use the graph routing algorithm of [LR99] and the constructive version of
Lovász Local Lemma [MT10] directly on the host expander graph. While this
simplifies the analysis, it also leads to a weaker dependence of the minor
size on $n$ than our first result.

Additionally, we show that expanders are the ‘most minor-rich’ family of graph
in the following sense. Using a simple counting technique, we show that for
every graph $G$ with $O(n)$ vertices and edges, there exists a graph $H$ with
$\Theta(n/\log n)$ vertices and edges, such that $H$ is not a minor of $G$. In
other words, expanders contain all graphs as minors with size up to this
fundamental limit for sparse graphs.

Independently from our work, Krivelevich and Nenadov [Kri19] provide an
elegant proof of a similar but stronger result. Their result achieves optimal
dependence on all three relevant parameters: $n$, the expansion of $G$, and
its maximum vertex-degree. They also provide an efficient algorithm that finds
such a minor in the host graph.

###  1.3 Longest Increasing Subsequence and Non-Crossing Matchings

Streaming algorithms have grown in importance in recent years due to the
massive amounts of data generated by modern applications such as network
monitoring, data mining, and machine learning. In these settings, traditional
‘efficient’ algorithms are no longer efficient because storing this massive
amount of data in memory for processing is impractical. In contrast, streaming
algorithms process data in a single pass and with limited memory, making them
a useful tool for handling such large-scale data sets. Over the last few
decades, there has been a significant body of work on the study of various
optimization problems in the streaming model, especially discrete optimization
problems and graph problems [Mut05, BYJK+02]. One such problem is the
classical Longest Increasing Subsequence (LIS) problem which naturally fits
into the streaming setting. In this problem, we are given a sequence
$S=(a_{1},\ldots,a_{N})$ of $N$ elements with the objective of estimating the
size of its longest increasing subsequence. Formally, we say that a
subsequence $S^{\prime}=(a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}})$ of length $k$
is an increasing subsequence of $S$ iff $1\leq i_{1}<i_{2}<\ldots<i_{k}\leq N$
and $a_{i_{1}}<a_{i_{2}}<\ldots<a_{i_{k}}$. In this section, we assume that
$S$ is a permutation of the _range_ $\left\\{1,\ldots,N\right\\}$ and each of
its elements can be stored in unit memory.

The LIS problem and its variants have been extensively studied in the
framework of streaming models and other related models. In the classical model
of computation, there is a textbook dynamic programming algorithm that solves
exactly computes LIS in $O(n^{2})$ time. Fredman [Fre75] improved this
algorithm to $O(n\log n)$ time using a technique that is now widely known and
used as ‘Patience Sorting.’ In the streaming model, the problem of computing
the exact length of LIS is very well understood: $\Theta(N)$ space is both
necessary and sufficient [LVZ06, GJKK07, SW07]. Thus, to achieve sublinear
space complexity, one must settle for an _approximate solution_ , where the
approximation factor, the ratio of the optimal length of LIS and the estimate
returned by an algorithm, serves as the measure of quality.

The approximability of deterministic streaming algorithms for the LIS problem
is equally well understood: $\Theta\left(\sqrt{\frac{{N}}{\alpha-1}}\right)$
space is both necessary and sufficient for achieving factor-$\alpha$
approximation to LIS length for any $\alpha>1$ [GJKK07, GG07, EJ08]. However,
approximability of randomized streaming algorithms remains wide open. No known
algorithm achieves strictly superior space complexity than deterministic ones,
while our understanding of lower bounds is elementary in this setting. The
only known lower bound result is due to Sun and Woodruff [SW07], who
established a lower bound of $\Omega(1/\epsilon)$ for the space complexity of
randomized algorithms that achieve a $(1+\epsilon)$-factor approximation
succeeding with probability at least $2/3$. In other words, even a
factor-$1.01$ approximation to LIS length in $O(1)$ space cannot be ruled out.

Motivated by this wide gap in our understanding of randomized streaming
algorithms for the LIS problem, we initiate the study of bipartite Non-
Crossing Matching (NCM) problem in the framework that we refer to as _hybrid
model_. In the NCM problem, we are given a bipartite graph $G=(L,R,E)$ with
ordered vertex sets $L$ and $R$. We say that a matching $M$ in $G$ is _non-
crossing_ if for every pair of edges $(u,v),(u^{\prime},v^{\prime})\in M$, if
$u<u^{\prime}$ then $v<v^{\prime}$ holds. The NCM problem is a generalization
of LIS problem in a sense, since a LIS problem instance $S$ can be thought of
as a NCM problem instance where all vertex-degrees are $1$. In the hybrid
model, we assume that the algorithm has the access to the graph $G=(L,R,E)$ as
follows. We are given access to vertices $L$ and $R$ beforehand, while the
edges of $G$ are revealed over the course of $|L|$ rounds. In the $i^{th}$
round, the algorithm is given a superset of edges incident on the $i^{th}$
vertex of $L$. It then selects a subset of these ‘advice-edges’ to _query_ ,
and then receives the set of ‘real-edges’ among its queried edge-slots. At the
end of processing the last vertex of $L$, the algorithm reports its estimate
on the cardinality of the maximum non-crossing matching in $G$. The aim in
this model is to minimize the number of queries per vertex as a fraction of
the number of advice-edges incident on it, while disregarding the space
complexity. In Chapter 4 of this thesis, we establish a connection between the
query complexity of the NCM problem in the hybrid model and the randomized
space complexity of the LIS problem in the streaming model. Our choice of the
hybrid model is motivated by the fact that understanding one problem is
closely linked to understanding the other.

There is a trivial algorithm in the hybrid model that queries every advice-
edge and exactly computes maximum non-crossing matching. We show that
improving on the number of edges queried by this trivial algorithm, by even a
small factor, has non-trivial consequences for the LIS problem. Specifically,
it would imply the existence of a randomized algorithm that achieves
factor-$N^{o(1)}$-approximation to LIS length in space $N^{1/2-\epsilon}$, for
some absolute constant $\epsilon$, which depends solely on the assumed
algorithm for the NCM problem in the hybrid model. We show a low space
complexity randomized LIS algorithm in the streaming model, that, without
reduction to the NCM problem, achieves factor $N^{o(1)}$-approximation with
low space complexity, except for input instances that satisfy some stringent
technical properties. For the latter case, we provide a structural result that
allows us to reduce LIS instances satisfying this technical condition to the
NCM problem in the hybrid model.

The intrinsic ‘self-reducibility’ or ‘self-summarizing’ property of the LIS
problem is the key ingredient in both, the explicit LIS algorithm and the
reduction to the NCM problem. This property enables us to obtain a
hierarchical decomposition of the input LIS instance $S$ and process the
instance differently at various ‘scales’. It facilitates a recursive sampling
based LIS streaming algorithm, that achieves the desired guarantee, except for
cases that meet the technical condition. Fortunately, the same technical
condition enables us to obtain a reduction to a collection of NCM problem
instances, each with a size of roughly $O(\log\log N)$, where $N$ is the
length of $S$. The constraints of the hybrid model allows us to simulate the
supposed NCM algorithm while processing $S$ in the streaming model, and the
hierarchical decomposition ensures that we perform a small number of parallel
executions of the NCM algorithm. Finally, the small NCM instance size enables
us to perform this simulation with an overhead of $N^{o(1)}$ in space
complexity. As a consequence, we reduce the problem of obtaining low space
complexity algorithm for the LIS problem in the streaming model to the problem
of obtaining low query complexity algorithm for the NCM problem in the hybrid
model.

We also establish a converse connection, that requires a technical restriction
of the streaming LIS algorithm. Specifically, we require that the algorithm is
_comparison-based_ , that is, it may only compare the values of the input
stream elements but not use their absolute values. We show that the existence
of factor-$(1+\epsilon)$ approximate comparison-based LIS streaming randomized
algorithm, for any sufficiently small constant $\epsilon>0$, implies a non-
trivial algorithm for the NCM problem in the hybrid model that significantly
outperforms the above-mentioned trivial algorithm. Our results thus
demonstrate that the space complexity of randomized streaming algorithms for
LIS problem is intrinsically linked to the query complexity of the NCM problem
in the hybrid model. This relationship between the LIS and NCM problems
highlights how graph-theoretic tools and graph-algorithmic techniques can
provide insights into the complexity of seemingly unrelated problems, even in
unconventional models of computation.

Exploiting the techniques developed in showing the equivalence of NCM and LIS
problems, we additionally show a randomized factor $\alpha$-approximation
algorithm for the LIS problem in the streaming model with space-complexity
$\tilde{O}\left(\frac{\sqrt{N}}{\alpha-1}\right)$ for any $\alpha>1$. This is
in contrast to the deterministic algorithms, which require space
$\Omega\left(\sqrt{\frac{N}{\alpha-1}}\right)$ achieving for
$\alpha$-approximation [GG07]. To the best of our knowledge, this is the first
known proof of separation of space complexity between deterministic and
randomized algorithms for the LIS problem in the streaming model.

##  Chapter 2 Node-Disjoint Paths

###  2.1 Introduction

In this chapter, we explore the classical Node-Disjoint Paths (NDP) problem
from the perspective of approximation algorithms and the hardness of
approximation. The problem’s input consists of an undirected graph $G$ with
$n$ vertices and a collection
${\mathcal{M}}=\left\\{(s_{1},t_{1}),\ldots,(s_{k},t_{k})\right\\}$ of $k$
vertex-pairs, called _source-destination_ or _demand_ pairs. We refer to the
vertices in set $S=\left\\{s_{1},\ldots,s_{k}\right\\}$ as _source vertices_ ;
to the vertices in set $T=\left\\{t_{1},\ldots,t_{k}\right\\}$ as _destination
vertices_ , and to the vertices in set $S\cup T$ collectively as _terminals_.
We say that a path $P$ _routes_ a demand pair $(s_{i},t_{i})$ iff the
endpoints of $P$ are $s_{i}$ and $t_{i}$. The goal of this problem is to
compute a maximum-cardinality set ${\mathcal{P}}$ of node-disjoint paths,
where each path $P\in{\mathcal{P}}$ routes a distinct demand pair in
${\mathcal{M}}$. The optimal solution size is denoted as
$\mathsf{OPT}_{\mathsf{NDP}}(G,{\mathcal{M}})$ or simply
$\mathsf{OPT}_{\mathsf{NDP}}$ when the instance is clear from the context.

While the original motivation for this problem came from its applications in
VLSI design, being a fundamental graph routing problem, it has been
extensively studied in both graph theory and theoretical computer science
communities. Robertson and Seymour [RS90, RS95] explored the problem in their
Graph Minor series, providing an efficient algorithm for NDP when 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 [Kar75, EIS76]. Consequently, the focus
of the research then naturally shifted to studying the NDP problem when the
underlying graph $G$ is ‘simpler’. Two special cases of NDP that have received
a lot of attention are when the underlying graph $G$ is a planar graph and
when it is a square grid. We denote the former problem as NDP-Planar and the
latter as NDP-Grid. 111We use the standard convention of denoting $n=|V(G)|$,
and so the underlying graph in the NDP-Grid instance is a grid graph $G$ with
$(\sqrt{n}\times\sqrt{n})$; we assume that $\sqrt{n}$ is an integer.. It is
worth noting that both of these special cases, NDP-Planar and NDP-Grid, are
NP-hard [Lyn75, KvL84]. We summarize the following known results in Table 2.1.

On the side of approximation algorithms, the best current approximation factor
of $O(\sqrt{n})$ for NDP is achieved by a simple greedy algorithm [KS04].
Until recently, this was also the best approximation algorithm for the above
mentioned special cases: NDP-Planar and NDP-Grid. From the direction of
hardness of approximation, before our work, only an
$\Omega(\log^{1/2-\epsilon}n)$-hardness of approximation was known for the NDP
problem, for any constant $\epsilon$, unless $\mbox{\sf NP}\subseteq\mbox{\sf
ZPTIME}(n^{\operatorname{poly}\log n})$ [AZ05, ACG+10]. In the special cases
of NDP-Planar and NDP-Grid, only APX-hardness was known [CK15]. The
approximability status of NDP remained wide open, and the designing better
approximation algorithms, especially in the conceivably simple setting of NDP-
Grid remained a tantalizing open question. Grid graphs are extremely well-
structured, and one might expect that good approximation algorithms can be
designed for them or, at the very least, that they should be easy to
understand. However, despite many efforts, various approximation techniques to
obtain sub-polynomial approximation factors failed for NDP-Grid and
establishing its approximability has remained elusive so far.

One natural technique of attacking NDP problem to design approximation
algorithms is via the standard multicommodity flow relaxation. Instead of
connecting (routed) demand pairs with a path, this technique involves sending
the maximum possible amount of (possibly fractional) flow between demand pairs
such that no vertex harbors more than one unit of flow. Such an optimal
fractional flow can be computed by writing a textbook linear program (LP) and
solving it optimally by standard methods. The hope is to ‘round’ this optimal
fractional solution and obtain a good feasible solution to the original NDP
problem. The approximation factor that we get is the ratio between the optimal
flow value and the size of rounded feasible solution to the NDP problem. The
$O(\sqrt{n})$-approximation algorithm of [KS04] can be cast as an LP-rounding
algorithm of precisely this multicommodity flow relaxation. Unfortunately, it
is well-known that the integrality gap of this relaxation is
$\Omega(\sqrt{n})$, even when the underlying graph is a grid, even with all
terminals lying on its boundary. In other words, there are NDP-Grid instances,
with terminals lying on the grid boundary, such that the optimal
multicommodity flow relaxation has value
$\Omega(\sqrt{n}\cdot\mathsf{OPT}_{\mathsf{NDP}})$ and we cannot hope to
achieve a $o(\sqrt{n})$-factor approximation with this approach.

Special Case | Approximation factor |  References
---|---|---
Constant $k$ | $1$ |  [RS90, RS95]
General Case | $O(n^{1/2})$ |  [KS04]
$\Omega(\log^{1/2-\epsilon}n)$ |  [AZ05, ACG+10]
$2^{\Omega(\sqrt{\log n})}$ |  [CKN17]
$n^{\Omega\left(1/(\log\log n)^{2}\right)}$ |  [CKN18a]
NDP-Grid | $\tilde{O}(n^{1/4})$ |  [CK15]
$n^{\Omega\left(1/(\log\log n)^{2}\right)}$ |  this thesis; see also [CKN18a]
NDP-Grid with sources on boundary | $2^{\tilde{O}(\sqrt{\log n})}$ |  [CKN18b]
NDP-Planar | $\tilde{O}(n^{9/19})$ |  [CKL16]
$2^{\Omega(\sqrt{\log n})}$ |  [CKN17]
$n^{\Omega\left(1/(\log\log n)^{2}\right)}$ |  this thesis; see also [CKN18a]
Table 2.1: Approximation tradeoffs for efficient algorithms for the NDP
problem in the general case and some special cases.

Bypassing this multicommodity flow integrality gap barrier, Chuzhoy and Kim
[CK15] designed an $\tilde{O}(n^{1/4})$-approximation for NDP-Grid; and along
with Li, generalized it to obtain an $\tilde{O}(n^{9/19})$-approximation
algorithm for NDP-Planar [CKL16]. Their key observation is that, if all
terminals lie close to the grid boundary, say within distance $O(n^{1/4})$ of
the grid boundary, then a simple dynamic programming-based algorithm yields an
$O(n^{1/4})$-approximation. On the other hand, if, for every demand pair,
either the source or the destination lies at a distance at least
$\Omega(n^{1/4})$ from the grid boundary, then the integrality gap of the
multicommodity flow relaxation improves, and one can obtain an
$\tilde{O}(n^{1/4})$-approximation via LP-rounding. A natural question is
whether the integrality gap for NDP-Grid improves even further, if all
terminals lie further away from the grid boundary. Unfortunately, the authors
show in [CK15] that the integrality gap remains at least $\Omega(n^{1/8})$,
even if all terminals lie within distance $\Omega(\sqrt{n})$ from the grid
boundary. A natural question then arises: is it possible to achieve better,
say sub-polynomial, factor of approximation when the terminals lie close to
the grid boundary? Or more specifically, can we improve over the simple
dynamic programming approach of [CK15] in this special case?

In our work [CKN18b], we answer this question in affirmative and show an
$2^{O\left(\sqrt{\log n}\cdot\log\log n\right)}$-approximation algorithm for
NDP-Grid provided all sources appear on the grid boundary. Note that we do not
require any restriction on the placement of the destination vertices: they may
appear anywhere on the underlying grid. As mentioned earlier, Chuzhoy and Kim
[CK15] show that the integrality gap of the multicommodity flow relaxation
problem remains $\Omega(n^{1/8})$ in this regime. To get around this barrier,
we define a new set of sufficient conditions. We show that we can efficiently
route each subset ${\mathcal{M}}^{\prime}\subseteq{\mathcal{M}}$ of demand
pairs that satisfies these conditions. We also show an efficient algorithm,
that given an NDP-Grid instance with sources lying on the grid boundary,
computes a subset ${\mathcal{M}}^{\prime}\subseteq{\mathcal{M}}$ of demand
pairs of cardinality $\mathsf{OPT}_{\mathsf{NDP}}/2^{O\left(\sqrt{\log
n}\cdot\log\log n\right)}$, that satisfy these sufficient conditions. We then
generalize our result to instances where the sources lie within a prescribed
distance from the grid boundary, at the expense of larger factor of
approximation.

In our earlier work [CKN17], we show that NDP-Planar (and hence, NDP) is hard
to approximate to within a $2^{\Omega(\sqrt{\log n})}$ factor unless
$\mbox{\sf NP}\subseteq\mbox{\sf DTIME}(n^{O(\log n)})$, even if the
underlying graph is a sub-cubic planar graph with all the sources lying on the
boundary of a single face. We also show that the same hardness of
approximation holds, even if the underlying graph is a subgraph of a grid
graph, with sources lying on the grid boundary. Equivalently, the underlying
graph of these hard instances is a grid graph with certain carefully chosen
vertices removed; and the demand pairs of these hard instances have sources
lying on the (original) grid boundary. Thus, our work [CKN18b] can be seen as
complementing this result. Together, they seem to suggest that sub-polynomial
approximation algorithms may be achievable for NDP-Grid and
$2^{\tilde{\Theta}(\sqrt{\log n})}$ might even be the ‘correct’ approximation
factor achievable.

In [CKN18a], we show that this is unlikely to be the case, and come close to
resolving the approximability status of NDP-Grid, and of NDP problem in
general. We show that NDP-Grid is $2^{\Omega(\log^{1-\epsilon}n)}$-hard to
approximate for any constant $\epsilon>0$ assuming ${\mbox{\sf
NP}\nsubseteq\mbox{\sf BPTIME}(n^{\operatorname{poly}\log n})}$. We further
show that it is $n^{\Omega\left(1/(\log\log n)^{2}\right)}$-hard to
approximate, assuming that for some constant $\delta>0$, $\mbox{\sf
NP}\not\subseteq\mbox{\sf RTIME}(2^{n^{\delta}})$. To show this hardness, we
perform a Cook reduction: if we have a good approximation efficient algorithm
for the NDP-Grid problem, we use it repeatedly to solve a known NP-Complete
3COL(5) problem. By choosing different tradeoffs between the NDP-Grid instance
sizes and the approximation factor, we obtain our hardness results. We note
that unlike the hard instances presented in [CKN17], the hard instances we
construct in this work require all terminals to be situated far away from the
boundary of the grid. This is in line with our earlier work in [CKN18b], where
we demonstrated an efficient algorithm with an improved approximation factor,
specifically designed for instances where the source vertices are in close
proximity to the grid boundary.

The NDP problem has been studied in a variety of restricted settings. Cutler
and Shiloach [CS78] studied a more restricted version of NDP-Grid, where all
source vertices lie on the top row $R^{*}$ of the grid, and all destination
vertices lie on a single row $R^{\prime}$ of the grid, far enough from its top
and bottom boundaries. We note that [CK15] extended their algorithm to a more
general setting, where the destination vertices may appear anywhere in the
grid, as long as the distance between any pair of the destination vertices,
and any destination vertex and the boundary of the grid, is large enough.
Robertson and Seymour [RS88] provided sufficient conditions for the existence
of node-disjoint routing of a given set of demand pairs in the more general
setting of graphs drawn on surfaces, and they designed an algorithm whose
running time scales at least exponentially in $k$, the number of demand pairs.
Their result implies the existence of the routing in grids, when the
destination vertices are sufficiently far from each other and from the grid
boundaries, but it does not provide an efficient algorithm to compute such a
routing. Aggarwal, Kleinberg, and Williamson [AKW00] considered another
special case of the NDP-Grid problem, where the set of the demand pairs is a
permutation: that is, every vertex of the grid participates in exactly one
demand pair. They show that $\Omega(\sqrt{n}/\log n)$ demand pairs are
routable in this case via node-disjoint paths.

Another basic routing problem that is closely related to NDP is the Edge-
Disjoint Paths (EDP) problem. The input to this problem is the same as before:
an undirected graph $G=(V,E)$ and a set
${\mathcal{M}}=\left\\{(s_{1},t_{1}),\ldots,(s_{k},t_{k})\right\\}$ 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,{\mathcal{M}})$, computing the line graph of the input
graph $G$ transforms it into an equivalent instance of NDP. However, this
transformation may potentially inflate the number of the graph vertices by a
quadratic factor, and so approximation factors that depend on $|V(G)|$ may no
longer be preserved. Moreover, this transformation does not preserve
planarity, and no relationship is known between NDP and EDP when the
underlying graph is constrained to be a planar graph.

The approximability status of EDP is very similar to that of NDP: the best
current approximation algorithm achieves an $O(\sqrt{n})$-approximation factor
[CKS06]. On the other side, until recently, our result [CKN17] showed the best
known $2^{\Omega(\sqrt{\log n})}$-hardness of approximation for EDP on planar
graphs, under the same complexity assumption. Interestingly, EDP appears to be
relatively easy on grid graphs, and has a constant-factor approximation for
this special case [AR95, KT98, KT95]. The analogue of NDP-Grid in the setting
of EDP seems to be the wall graph (see Figure 2.1): the approximability status
of EDP on wall graphs (that we call EDP-Wall) is similar to that of NDP-Grid.
Until recently, the best current upper bound was
$\tilde{O}(n^{1/4})$-approximation algorithm and the best lower bound was of
APX-hardness [CK15].

Figure 2.1: A wall graph.

Both of our results also extend to the EDP-Wall problem. In [CKN18b], we
extend our approximation algorithm for NDP-Grid to EDP-Wall when the sources
are located on the wall boundary. In [CKN18a], we show that the hardness of
approximation factor for NDP-Grid extends to EDP-Wall under the same
complexity assumptions. We note that for EDP on planar graphs (EDP-Planar),
the best upper bound is still $O(\sqrt{n})$, and it remains an open question
whether the techniques of [CKL16] that achieve an
$\tilde{O}(n^{9/19})$-approximation for NDP-Planar can be extended to EDP-
Planar.

Special Case | Approximation factor |  References
---|---|---
Constant $k$ | $1$ |  [RS90, RS95]
General Case | $O(n^{1/2})$ |  [CKS06]
$2^{\Omega(\sqrt{\log n})}$ |  [CKN17]
$n^{\Omega\left(1/(\log\log n)^{2}\right)}$ |  this thesis; see also [CKN18a]
EDP on grids, grid-like graphs and trees | $O(1)$ |  [AR95, AGLR94, KT98, KT95, GVY97, CMS07]
EDP on bounded-degree expanders and graphs with large minimum cut | $\tilde{O}(1)$ |  [LR99, BFU92, BFSU98, KR96, Fri01, RZ10]
EDP on Eulerian planar graphs and $4$-edge-connected planar graphs | $\tilde{O}(1)$ |  [KK13, Kle05]
EDP-Wall | $\tilde{O}(n^{1/4})$ |  [CK15]
$n^{\Omega\left(1/(\log\log n)^{2}\right)}$ |  this thesis; see also [CKN18a]
EDP-Planar | $\tilde{O}(n^{9/19})$ |  [CKL16]
$2^{\Omega(\sqrt{\log n})}$ |  [CKN17]
$n^{\Omega\left(1/(\log\log n)^{2}\right)}$ |  this thesis; see also [CKN18a]
Table 2.2: Approximation tradeoffs for efficient algorithms for the EDP
problem in the general case and some special cases.

As alluded earlier, unlike NDP, several other special cases of EDP are known
to have reasonably good approximation algorithms. We summarize some of the
following results in Table 2.2. For example, for the special case of Eulerian
planar graphs, Kleinberg [Kle05] showed an $O(\log^{2}n)$-approximation
algorithm, while Kawarabayashi and Kobayashi [KK13] provide an improved
$O(\log n)$-approximation for both Eulerian and $4$-connected planar graphs.
Bounded-degree expander graphs are also known to admit polylogarithmic
approximation algorithms [LR99, BFU94, BFSU98, KR96, Fri01]. Constant-factor
approximation algorithms are known for trees [GVY97, CMS07], as well as grids
and grid-like graphs [AR95, AGLR94, KT98, KT95]. Rao and Zhou [RZ10] showed an
efficient randomized polylogarithmic approximation algorithm for the special
case of EDP where underlying graphs have a large global minimum cut. Recently,
Fleszar et al. [FMS16] designed an $\tilde{O}(\sqrt{r})$-approximation
algorithm for EDP, where $r$ is the size of the feedback vertex set of $G$:
the smallest number of vertices that need to be deleted from $G$ in order to
turn it into a forest. Since $r\leq n$, their bound matches the result of
[CKS06] up to logarithmic factors and strengthens it when $r=o(n)$. In a
recent work, Huang et al. [HMM+21] showed a constant factor approximation
algorithm provided the underlying graph, together with the demand pairs
visualized as regular edges, forms a planar graph.

Another natural variant of NDP and EDP relaxes the the disjointedness
constraint by allowing a small vertex-congestion or edge-congestion has been a
subject of extensive study. In the NDP with Congestion (NDPwC) problem, the
input consists of an undirected graph and a set of demand pairs as before, and
additionally a non-negative integer $c$. The goal is to route a maximum number
of the demand pairs with congestion $c$, that is, each vertex may participate
in at most $c$ paths in the solution. The EDP with Congestion problem (EDPwC)
is defined similarly, except that now the congestion is measured on the graph
edges and not vertices. The famous result of Raghavan and Thompson [RT87],
that introduced the randomized LP-rounding technique, obtained a constant-
factor approximation for NDPwC and EDPwC, for a congestion value
$c=\Theta(\log n/\log\log n)$. A long sequence of work [CKS05, Räc02, And10,
RZ10, Chu16b, CL16, CE13, CC16a] has led to an $O(\operatorname{poly}\log
k)$-approximation for NDPwC and EDPwC with congestion bound $c=2$. This result
is essentially optimal, since it is known that for every constant $\epsilon$,
and for every congestion value $c=o(\log\log n/\log\log\log n)$, both problems
are hard to approximate to within a factor $\Omega((\log
n)^{\frac{1-\epsilon}{c+1}})$, unless $\mbox{\sf NP}\subseteq\mbox{\sf
ZPTIME}(n^{\operatorname{poly}\log n})$ [ACG+10]. When the input graph is
planar, Seguin-Charbonneau and Shepherd [SCS11], improving on the result of
Chekuri, Khanna and Shepherd [CKS09], have shown a constant-factor
approximation for EDPwC with congestion 2. Combined with these results, our
work shows a dramatic contrast in the approximability of EDP in the presence
of tiniest non-trivial congestion.

####  2.1.1 Our Results and Informal Overview of Techniques

Our main result is summarized in the following theorem:

######  Theorem 2.1.1.

For every constant $\epsilon>0$, there is no efficient
$2^{O(\log^{1-\epsilon}n)}$-approximation algorithm for the NDP problem,
assuming that $\mbox{\sf NP}\nsubseteq\mbox{\sf
RTIME}(n^{\operatorname{poly}\log n})$. Moreover, there is no efficient
$n^{O(1/(\log\log n)^{2})}$-approximation algorithm for the NDP problem,
assuming that for some constant $\delta>0$, $\mbox{\sf NP}\nsubseteq\mbox{\sf
RTIME}(2^{n^{\delta}})$. These results hold even when the input graph is a
grid graph or a wall graph.

We also extend this hardness of approximation result to the closely related
EDP problem under the same complexity assumptions. As mentioned earlier, EDP-
Wall can be thought of as an analogue to the NDP-Grid problem.

######  Theorem 2.1.2.

For every constant $\epsilon>0$, there is no efficient
$2^{O(\log^{1-\epsilon}n)}$-approximation algorithm for the EDP problem,
assuming that $\mbox{\sf NP}\nsubseteq\mbox{\sf
RTIME}(n^{\operatorname{poly}\log n})$. Moreover, there is no efficient
$n^{O(1/(\log\log n)^{2})}$-approximation algorithm for the EDP problem,
assuming that for some constant $\delta>0$, $\mbox{\sf NP}\nsubseteq\mbox{\sf
RTIME}(2^{n^{\delta}})$. These results hold even when the input graph is a
wall graph.

We now provide a high-level overview of our techniques behind the proof of
Theorem 2.1.1. We define a new graph partitioning problem, that we refer to as
(r,h)-Graph Partitioning Problem, and denote it by (r,h)-GP for short. In this
problem, we are given a bipartite graph $\tilde{G}=(V_{1},V_{2},E)$ along with
two integral parameters $r,h>0$. A solution to this problem is a partition
$(W_{1},W_{2},\ldots,W_{r})$ of $V_{1}\cup V_{2}$ into $r$ subsets, and for
each $1\leq i\leq r$, a subset $E_{i}\subseteq E(W_{i})$ of edges, so that
$|E_{i}|\leq h$ holds, and the goal is to maximize $\sum_{i=1}^{r}|E_{i}|$. We
say that a solution to (r,h)-GP is a _perfect solution_ if it has maximum
possible value: $r\cdot h$. An intuitive way to think about this problem is
that we would like to partition $\tilde{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.

Our goal is to show that NDP-Grid is at least as hard as (r,h)-GP for some
choice of parameters $r$ and $h$, and that (r,h)-GP itself is NP-hard to
approximate for the same choice of parameters. Unfortunately, despite our
feeling that (r,h)-GP is somewhat similar to Densest $k$-Subgraph problem
(DkS), we were unable to extend its hardness results to (r,h)-GP. 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\subseteq 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 $n^{1/4+\epsilon}$-approximation
for any constant $\epsilon$ [BCC+10]. Even though the problem appears to be
very hard to approximate, its hardness of approximation proof has been elusive
until recently: only constant-factor hardness results were known for DkS under
various worst-case complexity assumptions, and
$2^{\Omega(\log^{2/3}n)}$-hardness under average-case assumptions [Fei02,
AAM+11, Kho04, RS10]. In a recent breakthrough, Manurangsi [Man17] has shown
that for some constant $c$, DkS is hard to approximate to within a factor
$n^{1/(\log\log n)^{c}}$, under the Exponential Time Hypothesis. Even though
(r,h)-GP problem itself appears similar in flavor to DkS, we were unable to
extend the techniques of [Man17] 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 we call (r,h)-Graph Partitioning Problem with Bundles (or
(r,h)-GPwB for short), which is more general than (r,h)-GP. The definition of
this problem is somewhat technical and is deferred to Section 2.3.
Intuitively, we want this problem to be hard enough so that we can prove that
approximating it is NP-hard, but on the other hand, we also want it to be
‘easier’ than NDP-Grid, so that, we can show that good approximation algorithm
for NDP-Grid implies good approximation algorithm for (r,h)-GPwB. To this end,
we define subsets of edges in the underlying (r,h)-GPwB instance, that we call
bundles, and require that in each one of the $r$ subgraph, at most single edge
from a bundle can be present. As before, we say that a solution to (r,h)-GPwB
is a _perfect solution_ if it has maximum possible value: $r\cdot h$.

###### Relating NDP-Grid and (r,h)-GPwB.

Assume that we have an efficient $\alpha$-approximation algorithm
${\mathcal{A}}$ for NDP-Grid for some parameter $\alpha$. We show that, using
${\mathcal{A}}$, we can come up with an efficient algorithm
${\mathcal{A}}^{\prime}$ for (r,h)-GPwB with roughly the same approximation
factor. To this end, assume that we are given an instance
${\mathcal{I}}^{\prime}$ of (r,h)-GPwB problem and our goal is to come up with
an instance ${\mathcal{I}}$ of NDP-Grid such that ${\mathcal{I}}$ has large
solution iff ${\mathcal{I}}^{\prime}$ has a large solution. We can then use
the assumed efficient algorithm ${\mathcal{A}}$ on the NDP-Grid instance
${\mathcal{I}}$.

Intuitively, our reduction proceeds as follows. We start with a large enough
grid $G$ that will serve as the underlying graph for the NDP-Grid instance
${\mathcal{I}}$. The demand pairs ${\mathcal{M}}$ of ${\mathcal{I}}$
corresponds to the edges of (r,h)-GPwB instance ${\mathcal{I}}^{\prime}$: the
sources are placed in a single row far away from the grid boundary and
similarly, the destinations are placed in a single row far away from the grid
boundary and from the sources. We place the terminals in their respective rows
in a carefully chosen suitable random ordering. We now want to show that (i)
if the original (r,h)-GPwB instance ${\mathcal{I}}^{\prime}$ has a solution of
value $\beta$, then with constant probability, the NDP-Grid instance
${\mathcal{I}}$ has a solution routing roughly $\beta$ demand pairs; and (ii)
if we are given some feasible routing of $\beta$ demand pairs in the NDP-Grid
instance ${\mathcal{I}}$, we can efficiently come up with a feasible solution
of value roughly $\beta$ in the original (r,h)-GPwB instance
${\mathcal{I}}^{\prime}$.

For the first part, we define a notion of _distance property_. Intuitively, we
say that a set of demand pairs ${\mathcal{M}}$ has distance property if, for
every two demand pairs $(s,t),(s^{\prime},t^{\prime})\in{\mathcal{M}}$, the
distance between $t$ and $t^{\prime}$ is much larger than the same between $s$
and $s^{\prime}$. This separatedness allows us to show a combinatorial
algorithm, that given any set ${\mathcal{M}}^{\prime}$ of demand pairs with
distance property, routes them via node-disjoint paths. We then show that if
the optimum solution of (r,h)-GPwB instance ${\mathcal{I}}^{\prime}$ has value
$\beta$, then there is a subset of roughly $\beta$ demand pairs in the NDP-
Grid instance ${\mathcal{I}}$ with this distance property; and hence,
${\mathcal{I}}$ has a solution of value at least roughly $\beta$.

For the second part, we are given a node-disjoint routing of a subset
${\mathcal{M}}^{\prime}\subseteq{\mathcal{M}}$ of $\beta$ demand pairs of
${\mathcal{I}}$. Our goal is to show that the original (r,h)-GPwB instance
${\mathcal{I}}^{\prime}$ has a solution of value roughly $\min{(\beta,rh)}$.
We consider the underlying graph $G^{\prime}$ of ${\mathcal{I}}^{\prime}$ and
let $E^{\prime}$ be the subset of its edges corresponding to the demand pairs
in ${\mathcal{M}}^{\prime}$. We discard all but the edges $E^{\prime}$ from
$G^{\prime}$. Exploiting the fact that we have a node-disjoint routing of
demand pairs in ${\mathcal{M}}^{\prime}$ on a grid, and from our careful
placement of terminals on rows of the grid, we show that we can draw the graph
$G^{\prime}$ with relatively few crossings. We show that given such a drawing
of $G^{\prime}$ with few crossings, we can efficiently compute a good balanced
cut of $G^{\prime}$, where we divide $G^{\prime}$ into two subgraphs
$G^{\prime}_{1}$ and $G^{\prime}_{2}$, such that there are only a small number
of cut edges and the number of edges in $G^{\prime}_{1}$ and $G^{\prime}_{2}$
are roughly $|E^{\prime}|/2=\beta/2$. We repeat this process recursively until
we are left with $r$ subgraphs, each consisting of roughly $\beta/r$ edges. We
also show that we can perform this step while ensuring that each subgraph has
at most single edge from each bundle. Thus, we have computed a feasible
solution to the (r,h)-GPwB instance ${\mathcal{I}}^{\prime}$ of value roughly
$\min{(\beta,rh)}$.

Combining both these parts together, we show that if there is an efficient
$\alpha$-approximation algorithm for NDP-Grid, there is an efficient
$\tilde{\Omega}(\alpha)$-approximation algorithm for (r,h)-GPwB.

###### Hardness of (r,h)-GPwB.

The high level overview of the reduction to show that (r,h)-GPwB itself is
hard, is as follows. We perform a reduction from a known NP-Complete problem
3COL(5), which is a special case of the $3$-coloring problem, where the
underlying graph is $5$-regular. It is well known that there is some constant
$\epsilon$, such that it is NP-Hard to distinguish between its Yes-Instance
(the input graph is vertex-colorable by three colors such that no edge is
monochromatic) and No-Instance (for every three-coloring, at least an
$\epsilon$-fraction of the edges are monochromatic) [FHKS03]. We start with a
3COL(5) instance $G^{*}$ and a parameter $\ell>0$, that depends on the
approximation factor $\alpha$ that we are considering. We construct a
bipartite constraint graph $H$ with the following properties. The vertices of
$H$ on one side correspond to $\ell$-tuples of edges of $G^{*}$; and the
vertices on its other side correspond to $\ell$-tuples of vertices of $G^{*}$.
There is an edge between two vertices if the other vertex corresponds to a
tuple of endpoints of the edges corresponding to the first vertex. We then
consider a ‘cover-graph’ $L(H)$, where each vertex of $H$ is replaced by a
cloud of vertices taking into account potential feasible colorings of the
original graph $G^{*}$. We also analogously define cover-graph $L(H^{\prime})$
for each subgraph $H^{\prime}$ of $H$. For each subgraph $H^{\prime}$ of $H$,
we think of this cover-graph $L(H^{\prime})$ as an instance of (r,h)-GPwB for
some suitable choice of parameters $r$ and $h$ depending upon $\ell$ and the
size of the graph $H^{\prime}$.

We show that if $G^{*}$ is a Yes-Instance, the corresponding (r,h)-GPwB
instance $L(H)$ has a perfect solution. In fact, we can also show that if
$G^{*}$ is a Yes-Instance, for every subgraph $H^{\prime}$ of $H$, the
corresponding (r,h)-GPwB instance $L(H^{\prime})$ has a perfect solution.
Ideally we would like to show that if $G^{*}$ is a No-Instance, the (r,h)-GPwB
instance has small optimal solution. Indeed if that is the case, we can then
use the assumed efficient approximation algorithm ${\mathcal{A}}^{\prime}$ for
(r,h)-GPwB to distinguish between the Yes-Instance and No-Instance of 3COL(5)
problem, proving that approximating (r,h)-GPwB is NP-Hard. Unfortunately, it
might still be possible that $L(H)$ has a large feasible solution even though
$G^{*}$ is a No-Instance.

To overcome this issue, we employ an iterative Cook-type reduction. In every
iteration $j$, we reduce the 3COL(5) instance $G^{*}$ to a collection
${\mathcal{I}}_{j}$ of instances of (r,h)-GPwB, corresponding to a collection
${\mathcal{H}}_{j}$ of the subgraphs of $H$; and apply the algorithm
${\mathcal{A}}^{\prime}$ to each of them. If $G^{*}$ is a Yes-Instance, then
we show that each resulting instance of (r,h)-GPwB has perfect solution, and
so all solutions returned by ${\mathcal{A}}^{\prime}$ are large. If on the
other hand, $G^{*}$ is a No-Instance, it is still possible that the resulting
instances of (r,h)-GPwB will have large solutions, or even perfect solutions.
However, we can use these resulting solutions in order to further refine our
reduction, and construct a new collection ${\mathcal{I}}_{j+1}$ of instances
of (r,h)-GPwB, corresponding to a fresh collection ${\mathcal{H}}_{j+1}$ of
the subgraphs of $H$. While in the Yes-Instance case we will continue to
obtain large solutions to all (r,h)-GPwB instances that we construct, we can
show that in the No-Instance case, in some iteration of the algorithm, we will
fail to find such a large solution. Our reduction is crucially sequential, and
we exploit the solutions returned by algorithm ${\mathcal{A}}^{\prime}$ in
previous iterations in order to construct new instances of (r,h)-GPwB for the
subsequent iterations.

We show that the running time of our reduction is polynomial in the size of
$H$: which itself scales as $N^{\ell+O(1)}$, where $N$ is the number of
vertices in the original 3COL(5) instance $G^{*}$. Recall that the choice of
$\ell$ depends upon the approximation factor $\alpha$. Performing tradeoffs
between the different values for $\alpha$ and the resulting running time, we
obtain the guarantees of Theorem 2.1.1.

####  2.1.2 Organization

We start with Preliminaries in Section 2.2, and introduce the new graph
partitioning problems in Section 2.3. The hardness of approximation proof for
NDP-Grid appears in Section 2.4, with the reduction from the graph
partitioning problem to NDP-Grid deferred to Section 2.5. Finally, we extend
our hardness results to NDP-Wall and EDP-Wall in Section 2.6.

###  2.2 Preliminaries

We use standard graph-theoretic notation. Given a graph $G$ and a subset
$W\subseteq V(G)$ of its vertices, $E(W)$ denotes the set of all edges of $G$
that have both their endpoints in $W$. Given a path $P$ and a subset $U$ of
vertices of $G$, we say that $P$ is _internally disjoint_ from $U$ iff every
vertex in $P\cap U$ is an endpoint of $P$. Similarly, $P$ is internally
disjoint from a subgraph $G^{\prime}$ of $G$ iff $P$ is internally disjoint
from $V(G^{\prime})$. Given a subset
${\mathcal{M}}^{\prime}\subseteq{\mathcal{M}}$ of the demand pairs in $G$, we
denote by $S({\mathcal{M}}^{\prime})$ and $T({\mathcal{M}}^{\prime})$ the sets
of the source and the destination vertices of the demand pairs in
${\mathcal{M}}^{\prime}$, respectively. We let
${\mathcal{T}}({\mathcal{M}}^{\prime})=S({\mathcal{M}}^{\prime})\cup
T({\mathcal{M}}^{\prime})$ denote the set of all terminals participating as a
source or a destination in ${\mathcal{M}}^{\prime}$. All logarithms in this
paper are to the base of 2.

###### Grid Graphs.

For a pair $h,\ell>0$ of integers, we let $G^{h,\ell}$ denote the grid of
height $h$ and length $\ell$. The set of its vertices is
$V(G^{h,\ell})=\left\\{v(i,j)\mid 1\leq i\leq h,1\leq j\leq\ell\right\\}$, and
the set of its edges is the union of two subsets: the set
$E^{H}=\left\\{(v_{i,j},v_{i,j+1})\mid 1\leq i\leq h,1\leq j<\ell\right\\}$ of
horizontal edges and the set $E^{V}=\left\\{(v_{i,j},v_{i+1,j})\mid 1\leq
i<h,1\leq j\leq\ell\right\\}$ of vertical edges. The subgraph of $G^{h,\ell}$
induced by the edges of $E^{H}$ consists of $h$ paths, that we call the _rows_
of the grid; for $1\leq i\leq h$, the $i$th row $R_{i}$ is the row containing
the vertex $v(i,1)$. Similarly, the subgraph induced by the edges of $E^{V}$
consists of $\ell$ paths that we call the _columns_ of the grid, and for
$1\leq j\leq\ell$, the $j$th 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
$\operatorname{row}(v)$ and $\operatorname{col}(v)$ the row and the column of
the grid, respectively, that contain $v$. We say that $G^{h,\ell}$ is a
_square grid_ iff $h=\ell$. The _boundary of the grid_ is $R_{1}\cup R_{h}\cup
W_{1}\cup W_{\ell}$. We sometimes refer to $R_{1}$ and $R_{h}$ as the top and
the bottom boundary edges of the grid respectively, and to $W_{1}$ and
$W_{\ell}$ as the left and the right boundary edges of the grid.

Given a subset ${\mathcal{R}}^{\prime}$ of consecutive rows of $G$ and a
subset ${\mathcal{W}}^{\prime}$ of consecutive columns of $G$, the _sub-grid
of $G$ spanned by the rows in ${\mathcal{R}}^{\prime}$ and the columns in
${\mathcal{W}}^{\prime}$_ is the sub-graph of $G$ induced by the set
$\left\\{v\mid\operatorname{row}(v)\in{\mathcal{R}}^{\prime},\operatorname{col}(v)\in{\mathcal{W}}^{\prime}\right\\}$
of its vertices.

Given two vertices $u=v(i,j)$ and $u^{\prime}=v(i^{\prime},j^{\prime})$ of a
grid $G$, the shortest-path distance between them is denoted by
$d(u,u^{\prime})$. Given two vertex subsets $X,Y\subseteq V(G)$, the distance
between them is $d(X,Y)=\min_{u\in X,u^{\prime}\in
Y}\left\\{d(u,u^{\prime})\right\\}$. When $H,H^{\prime}$ are subgraphs of $G$,
we use $d(H,H^{\prime})$ to denote $d(V(H),V(H^{\prime}))$.

###### Wall Graphs.

Let $G=G^{\ell,h}$ be a grid of length $\ell$ and height $h$. Assume that
$\ell>0$ is an even integer, and that $h>0$. For every column $W_{j}$ of the
grid, let $e^{j}_{1},\ldots,e^{j}_{h-1}$ be the edges of $W_{j}$ indexed in
their top-to-bottom order. Let $E^{*}(G)\subseteq E(G)$ contain all edges
$e^{j}_{z}$, where $z\neq j\mod 2$, and let $\hat{G}$ be the graph obtained
from $G\setminus E^{*}(G)$, by deleting all degree-$1$ vertices from it. Graph
$\hat{G}$ is called a _wall of length $\ell/2$ and height $h$_ (see Figure
2.1). Consider the subgraph of $\hat{G}$ induced by all horizontal edges of
the grid $G$ that belong to $\hat{G}$. This graph is a collection of $h$ node-
disjoint paths, that we refer to as the _rows_ of $\hat{G}$, and denote them
by $R_{1},\ldots,R_{h}$ in this top-to-bottom order; notice that $R_{j}$ is
also the $j$th row of the grid $G$ for all $j$. Graph $\hat{G}$ contains a
unique collection ${\mathcal{W}}$ of $\ell/2$ node-disjoint paths that connect
vertices of $R_{1}$ to vertices of $R_{h}$ and are internally disjoint from
$R_{1}$ and $R_{h}$. We refer to the paths in ${\mathcal{W}}$ as the _columns_
of $\hat{G}$, and denote them by $W_{1},\ldots,W_{\ell/2}$ in this left-to-
right order. Paths $W_{1},W_{\ell/2},R_{1}$ and $R_{h}$ are called the left,
right, top and bottom boundary edges of $\hat{G}$, respectively, and their
union is the boundary of $\hat{G}$.

###### The 3COL(5) problem.

The starting point of our reduction is the 3COL(5) problem. In this problem,
we are given a $5$-regular graph $G=(V,E)$. Note that, if $n=|V|$ and $m=|E|$,
then $m=5n/2$. We are also given a set ${\mathcal{C}}=\left\\{r,b,g\right\\}$
of $3$ colors. A _coloring_ $\chi:V\rightarrow{\mathcal{C}}$ is an assignment
of a color in ${\mathcal{C}}$ to every vertex in $V$. We say that an edge
$e=(u,v)$ is _satisfied_ by the coloring $\chi$ iff $\chi(u)\neq\chi(v)$. The
coloring $\chi$ is _valid_ iff it satisfies every edge. We say that $G$ is a
Yes-Instance iff there is a valid coloring $\chi:V\rightarrow{\mathcal{C}}$.
We say that it is a No-Instance with respect to some given parameter
$\epsilon$, iff for every coloring $\chi:V\rightarrow{\mathcal{C}}$, at most a
$(1-\epsilon)$-fraction of the edges are satisfied by $\chi$. We use the
following theorem of Feige et al. [FHKS03]:

######  Theorem 2.2.1.

[Proposition 15 in [FHKS03]] There is some constant $\epsilon$, such that
distinguishing between the Yes-Instances and the No-Instances (with respect to
$\epsilon$) of 3COL(5) is NP-hard.

###### A Two-Prover Protocol.

We use the following two-prover protocol. The two provers are called an edge-
prover and a vertex-prover. Given a $5$-regular graph $G$, the verifier
selects an edge $e=(u,v)$ of $G$ uniformly at random, and then selects a
random endpoint (say $v$) of this edge. It then sends $e$ to the edge-prover
and $v$ to the vertex-prover. The edge-prover must return an assignment of
colors from ${\mathcal{C}}$ to $u$ and $v$, such that the two colors are
distinct; the vertex-prover must return an assignment of a color from
${\mathcal{C}}$ to $v$. The verifier accepts iff both provers assign the same
color to $v$. Given a $2$-prover game ${\mathcal{G}}$, its _value_ is the
maximum acceptance probability of the verifier over all possible strategies of
the provers.

Notice that, if $G$ is a Yes-Instance, then there is a strategy for both
provers that guarantees acceptance with probability $1$: the provers fix a
valid coloring $\chi:V\rightarrow{\mathcal{C}}$ of $G$ and respond to the
queries according to this coloring.

We claim that if $G$ is a No-Instance, then for any strategy of the two
provers, the verifier accepts with probability at most $(1-\epsilon/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 $Q^{\prime}$, 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 $\epsilon m$ edges.
The probability that the verifier chooses one of these edge is at least
$\epsilon$. 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 $\frac{1}{2}$, and so
overall the verifier rejects with probability at least $\epsilon/2$.
Therefore, if $G$ is a Yes-Instance, then the value of the corresponding game
is $1$, and if it is a No-Instance, then the value of the game is at most
$(1-\epsilon/2)$.

###### Parallel Repetition.

We perform $\ell$ rounds of parallel repetition of the above protocol, for
some integer $\ell>0$, that may depend on $n=|V(G)|$. Specifically, the
verifier chooses a sequence $(e_{1},\ldots,e_{\ell})$ of $\ell$ edges, where
each edge $e_{i}$ is selected independently uniformly at random from $E(G)$.
For each chosen edge $e_{i}$, one of its endpoints $v_{i}$ is then chosen
independently at random. The verifier sends $(e_{1},\ldots,e_{\ell})$ to the
edge-prover, and $(v_{1},\ldots,v_{\ell})$ to the vertex-prover. The edge-
prover returns a coloring of both endpoints of each edge $e_{i}$. 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 $e_{i}$ 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 $(v_{1},\ldots,v_{\ell})$. Again,
if some vertex $v_{i}$ repeats twice, the coloring of the two occurrences need
not be consistent. The verifier accepts iff for each $1\leq i\leq\ell$, the
coloring of the vertex $v_{i}$ returned by both provers is consistent. (No
verification of consistency is performed across different $i$’s. So, for
example, if $v_{i}$ is an endpoint of $e_{j}$ for $i\neq j$, then it is
possible that the two colorings do not agree and the verifier still accepts).
We say that a pair $(A,A^{\prime})$ of answers to the two queries
$(e_{1},\ldots,e_{\ell})$ and $(v_{1},\ldots,v_{\ell})$ is _matching_ , or
_consistent_ , iff it causes the verifier to accept. We let
${\mathcal{G}}^{\ell}$ denote this 2-prover protocol with $\ell$ repetitions.

######  Theorem 2.2.2 (Parallel Repetition).

[Raz98, Hol07, Rao08] There is some constant $0<\gamma^{\prime}<1$, such that
for each $2$-prover game $\tilde{\mathcal{G}}$, if the value of
$\tilde{\mathcal{G}}$ is $x$, then the value of the game
$\tilde{\mathcal{G}}^{\ell}$, obtained from $\ell>0$ parallel repetitions of
$\tilde{\mathcal{G}}$, is $x^{\gamma^{\prime}\ell}$.

######  Corollary 2.2.3.

There is some constant $0<\gamma<1$, such that, if $G$ is a Yes-Instance, then
${\mathcal{G}}^{\ell}$ has value $1$, and if $G$ is a No-Instance, then
${\mathcal{G}}^{\ell}$ has value at most $2^{-\gamma\ell}$.

We now summarize the parameters and introduce some basic notation:

  * •

Let ${\mathcal{Q}}^{E}$ denote the set of all possible queries to the edge-
prover, so each query is an $\ell$-tuple of edges. Then
$|{\mathcal{Q}}^{E}|=m^{\ell}=(5n/2)^{\ell}$. Each query has $6^{\ell}$
possible answers – $6$ colorings per edge. The set of feasible answers is the
same for each edge-query, and we denote it by ${\mathcal{A}}^{E}$.

  * •

Let ${\mathcal{Q}}^{V}$ denote the set of all possible queries to the vertex-
prover, so each query is an $\ell$-tuple of vertices. Then
$|{\mathcal{Q}}^{V}|=n^{\ell}$. Each query has $3^{\ell}$ feasible answers –
$3$ colorings per vertex. The set of feasible answers is the same for each
vertex-query, and we denote it by ${\mathcal{A}}^{V}$.

  * •

We think about the verifier as choosing a number of random bits, that
determine the choices of the queries $Q\in{\mathcal{Q}}^{E}$ and
$Q^{\prime}\in{\mathcal{Q}}^{V}$ 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 ${\mathcal{R}}$, where for each $R\in{\mathcal{R}}$, we denote
$R=(Q,Q^{\prime})$, with $Q\in{\mathcal{Q}}^{E}$,
$Q^{\prime}\in{\mathcal{Q}}^{V}$ — the two queries sent to the two provers
when the verifier chooses $R$. Then $|{\mathcal{R}}|=(2m)^{\ell}=(5n)^{\ell}$,
and each random string $R\in{\mathcal{R}}$ is chosen with the same
probability.

  * •

It is important to note that each query
$Q=(e_{1},\ldots,e_{\ell})\in{\mathcal{Q}}^{E}$ of the edge-prover
participates in exactly $2^{\ell}$ random strings (one random string for each
choice of one endpoint per edge of $\left\\{e_{1},\ldots,e_{\ell}\right\\}$),
while each query $Q^{\prime}=(v_{1},\ldots,v_{\ell})$ of the vertex-prover
participates in exactly $5^{\ell}$ random strings (one random string for each
choice of an edge incident to each of $v_{1},\ldots,v_{\ell}$).

A function
$f:{\mathcal{Q}}^{E}\cup{\mathcal{Q}}^{V}\rightarrow{\mathcal{A}}^{E}\cup{\mathcal{A}}^{V}$
is called a _global assignment of answers to queries_ iff for every query
$Q\in{\mathcal{Q}}^{E}$ to the edge-prover, $f(Q)\in{\mathcal{A}}^{E}$, and
for every query $Q^{\prime}\in{\mathcal{Q}}^{V}$ to the vertex-prover,
$f(Q^{\prime})\in{\mathcal{A}}^{V}$. We say that $f$ is a _perfect global
assignment_ iff for every random string $R=(Q^{E},Q^{V})$,
$(f(Q^{E}),f(Q^{V}))$ is a matching pair of answers. The following simple
theorem, whose proof appears in Section A.1.0.1 of the Appendix, shows that in
the Yes-Instance, there are many perfect global assignments, that neatly
partition all answers to the edge-queries.

######  Theorem 2.2.4.

Assume that $G$ is a Yes-Instance. Then there are $6^{\ell}$ perfect global
assignments $f_{1},\ldots,f_{6^{\ell}}$ of answers to queries, such that:

  * •

for each query $Q\in{\mathcal{Q}}^{E}$ to the edge-prover, for each possible
answer $A\in{\mathcal{A}}^{E}$, there is exactly one index $1\leq i\leq
6^{\ell}$ with $f_{i}(Q)=A$; and

  * •

for each query $Q^{\prime}\in{\mathcal{Q}}^{V}$ to the vertex-prover, for each
possible answer $A^{\prime}\in{\mathcal{A}}^{V}$ to $Q^{\prime}$, there are
exactly $2^{\ell}$ indices $1\leq i\leq 6^{\ell}$, for which
$f_{i}(Q^{\prime})=A^{\prime}$.

###### Two Graphs.

Given a 3COL(5) instance $G$ with $|V(G)|=n$, and an integer $\ell>0$, we
associate a graph $H$, that we call the _constraint graph_ , with it. For
every query $Q\in{\mathcal{Q}}^{E}\cup{\mathcal{Q}}^{V}$, there is a vertex
$v(Q)$ in $H$, while for each random string $R=(Q,Q^{\prime})$, there is an
edge $e(R)=(v(Q),v(Q^{\prime}))$. 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)^{\ell}$, $|U^{V}|=n^{\ell}$; the degree of every
vertex in $U^{E}$ is $2^{\ell}$; the degree of every vertex in $U^{V}$ is
$5^{\ell}$, and $|E(H)|=|{\mathcal{R}}|=(5n)^{\ell}$.

Assume now that we are given some subgraph $H^{\prime}\subseteq H$ of the
constraint graph. We build a bipartite graph $L(H^{\prime})$ associated with
it (this graph takes into account the answers to the queries; it may be
convenient for now to think that $H^{\prime}=H$, but later we will use smaller
sub-graphs of $H$). The vertices of $L(H^{\prime})$ are partitioned into two
subsets:

  * •

For each edge-query $Q\in{\mathcal{Q}}^{E}$ with $v(Q)\in H^{\prime}$, for
each possible answer $A\in{\mathcal{A}}^{E}$ to $Q$, we introduce a vertex
$v(Q,A)$. We denote by $S(Q)$ the set of these $6^{\ell}$ vertices
corresponding to $Q$, and we call them a _group representing $Q$_. We denote
by $\hat{U}^{E}$ the resulting set of vertices:

$\hat{U}^{E}=\left\\{v(Q,A)\mid(Q\in{\mathcal{Q}}^{E}\mbox{ and }v(Q)\in
H^{\prime}),A\in{\mathcal{A}}^{E}\right\\}.$

  * •

For each vertex-query $Q^{\prime}\in{\mathcal{Q}}^{V}$ with $v(Q^{\prime})\in
H^{\prime}$, for each possible answer $A^{\prime}\in{\mathcal{A}}^{V}$ to
$Q^{\prime}$, we introduce $2^{\ell}$ vertices
$v_{1}(Q^{\prime},A^{\prime}),\ldots,v_{2^{\ell}}(Q^{\prime},A^{\prime})$. We
call all these vertices _the copies of answer $A^{\prime}$ to query
$Q^{\prime}$_. We denote by $S(Q^{\prime})$ the set of all vertices
corresponding to $Q^{\prime}$:

$S(Q^{\prime})=\left\\{v_{i}(Q^{\prime},A^{\prime})\mid
A^{\prime}\in{\mathcal{A}}^{V},1\leq i\leq 2^{\ell}\right\\},$

so $|S(Q^{\prime})|=6^{\ell}$. We call $S(Q^{\prime})$ _the group representing
$Q^{\prime}$_. We denote by $\hat{U}^{V}$ the resulting set of vertices:

$\hat{U}^{V}=\left\\{v_{i}(Q^{\prime},A^{\prime})\mid(Q^{\prime}\in{\mathcal{Q}}^{V}\mbox{
and }v(Q^{\prime})\in H^{\prime}),A^{\prime}\in{\mathcal{A}}^{V},1\leq i\leq
2^{\ell}\right\\}.$

The final set of vertices of $L(H^{\prime})$ is $\hat{U}^{E}\cup\hat{U}^{V}$.
We define the set of edges of $L(H^{\prime})$ as follows. For each random
string $R=(Q^{E},Q^{V})$ whose corresponding edge $e(R)$ belongs to
$H^{\prime}$, for every answer $A\in{\mathcal{A}}^{E}$ to $Q^{E}$, let
$A^{\prime}\in{\mathcal{A}}^{V}$ be the unique answer to $Q^{V}$ consistent
with $A$. For each copy $v_{i}(Q^{V},A^{\prime})$ of answer $A^{\prime}$ to
query $Q^{V}$, we add an edge $(v(Q^{E},A),v_{i}(Q^{V},A^{\prime}))$. Let

$E(R)=\left\\{(v(Q^{E},A),v_{i}(Q^{V},A^{\prime}))\mid
A\in{\mathcal{A}}^{E},A^{\prime}\in{\mathcal{A}}^{V},\mbox{ $A$ and
$A^{\prime}$ are consistent answers to $R$},1\leq i\leq 2^{\ell}\right\\}$

be the set of the resulting edges, so $|E(R)|=6^{\ell}\cdot
2^{\ell}=12^{\ell}$. We denote by $\hat{E}$ the set of all edges of
$L(H^{\prime})$ — the union of the sets $E(R)$ for all random strings $R$ with
$e(R)\in H^{\prime}$.

Recall that we have defined a partition of the set $\hat{U}^{E}$ of vertices
into groups $S(Q)$ — one group for each query $Q\in{\mathcal{Q}}^{E}$ with
$v(Q)\in H^{\prime}$. We denote this partition by ${\mathcal{U}}_{1}$.
Similarly, we have defined a partition of $\hat{U}^{V}$ into groups, that we
denote by ${\mathcal{U}}_{2}=\left\\{S(Q^{\prime})\mid
Q^{\prime}\in{\mathcal{Q}}^{V}\mbox{ and }v(Q^{\prime})\in
H^{\prime}\right\\}$. Recall that for each group
$U\in{\mathcal{U}}_{1}\cup{\mathcal{U}}_{2}$, $|U|=6^{\ell}$.

Finally, we need to define bundles of edges in graph $L(H^{\prime})$. For
every vertex $v\in\hat{U}^{E}\cup\hat{U}^{V}$, we define a partition
${\mathcal{B}}(v)$ of the set of all edges incident to $v$ in $L(H^{\prime})$
into bundles, as follows. Fix some group
$U\in{\mathcal{U}}_{1}\cup{\mathcal{U}}_{2}$ that we have defined. If there is
at least one edge of $L(H^{\prime})$ 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 ${\mathcal{B}}(v)$. Therefore, if $v\in S(Q)$,
then for each random string $R$ in which $Q$ participates, with $e(R)\in
H^{\prime}$, we have defined one bundle of edges in ${\mathcal{B}}(v)$. For
each vertex $v\in\hat{U}^{E}\cup\hat{U}^{V}$, the set of all edges incident to
$v$ is thus partitioned into a collection of bundles, that we denote by
${\mathcal{B}}(v)$, and we denote $\beta(v)=|{\mathcal{B}}(v)|$. Note that, if
$v\in S(Q)$ for some query $Q\in{\mathcal{Q}}^{E}\cup{\mathcal{Q}}^{V}$, then
$\beta(v)$ is exactly the degree of the vertex $v(Q)$ in graph $H^{\prime}$.
Note also that $\bigcup_{v\in V(H^{\prime})}{\mathcal{B}}(v)$ does not define
a partition of the edges of $\hat{E}$, as each such edge belongs to two
bundles. However, each of $\bigcup_{v\in\hat{U}^{E}}{\mathcal{B}}(v)$ and
$\bigcup_{v\in\hat{U}^{V}}{\mathcal{B}}(v)$ does define a partition of
$\hat{E}$. It is easy to verify that every bundle that we have defined
contains exactly $2^{\ell}$ edges.

###  2.3 The (r,h)-Graph Partitioning Problem with Bundles

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 $\tilde{G}=(V_{1},V_{2},E)$ and two integral
parameters $h,r>0$. A solution consists of a partition $(W_{1},\ldots,W_{r})$
of $V_{1}\cup V_{2}$ into $r$ subsets, and for each $1\leq i\leq r$, a subset
$E_{i}\subseteq E(W_{i})$ of edges, such that $|E_{i}|\leq h$. The goal is to
maximize $\sum_{i}|E_{i}|$.

One intuitive way to think about the (r,h)-GP problem is that we would like to
partition the vertices of $\tilde{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 $\tilde{G}$ (the subgraphs
$\tilde{G}[W_{i}]$), but unlike DkS, where we only need to find one such dense
subgraph, we would like to partition all vertices of $\tilde{G}$ into a
prescribed number of dense subgraphs. We can prove that NDP-Grid is at least
as hard as (r,h)-GP (to within polylogarithmic factors; see below), but
unfortunately we could not prove strong hardness of approximation results for
(r,h)-GP. In particular, known hardness proofs for DkS do not seem to
generalize to this problem. To overcome this difficulty, we define a slightly
more general problem, and then use it as a proxy in our reduction. Before
defining the more general problem, we start with intuition.

###### Intuition:

Given a 3COL(5) instance $G$, we can construct the graph $H$, and the graph
$L(H)$, as described above. We can then view $L(H)$ as an instance of
(r,h)-GP, with $r=6^{\ell}$ and $h=|{\mathcal{R}}|$. Assume that $G$ is a Yes-
Instance. Then we can use the perfect global assignments $f_{1},\ldots,f_{r}$
of answers to the queries, given by Theorem 2.2.4, in order to partition the
vertices of $L(H)$ into $r=6^{\ell}$ clusters $W_{1},\ldots,W_{r}$, as
follows. Fix some $1\leq i\leq r$. For each query $Q\in{\mathcal{Q}}^{E}$ to
the edge-prover, set $W_{i}$ contains a single vertex $v(Q,A)\in S(Q)$, where
$A=f_{i}(Q)$. For each query $Q^{\prime}\in{\mathcal{Q}}^{V}$ to the vertex-
prover, set $W_{i}$ contains a single vertex $v_{j}(Q^{\prime},A^{\prime})$,
where $A^{\prime}=f_{i}(Q^{\prime})$, and the indices $j$ are chosen so that
every vertex $v_{j}(Q^{\prime},A^{\prime})$ participates in exactly one
cluster $W_{i}$. From the construction of the graph $L(H)$ and the properties
of the assignments $f_{i}$ guaranteed by Theorem 2.2.4, we indeed obtain a
partition $W_{1},\ldots,W_{r}$ of the vertices of $L(H)$. For each $1\leq
i\leq r$, we then set $E_{i}=E(W_{i})$. Notice that for every query
$Q\in{\mathcal{Q}}^{E}\cup{\mathcal{Q}}^{V}$, exactly one vertex of $S(Q)$
participates in each cluster $W_{i}$. Therefore, for each group
$U\in{\mathcal{U}}_{1}\cup{\mathcal{U}}_{2}$, each cluster $W_{i}$ contains
exactly one vertex from this group. It is easy to verify that for each $1\leq
i\leq r$, for each random string $R\in{\mathcal{R}}$, set $E_{i}$ contains
exactly one edge of $E(R)$, and so $|E_{i}|=|{\mathcal{R}}|=h$, and the
solution value is $h\cdot r$. Unfortunately, in the No-Instance, we may still
obtain a solution of a high value, as follows: instead of distributing, for
each query $Q\in{\mathcal{Q}}^{E}\cup{\mathcal{Q}}^{V}$, the vertices of
$S(Q)$ to different clusters $W_{i}$, 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 solutions222We note that a similar
problem arises if one attempts to design naïve hardness of approximation
proofs for DkS.. Moreover, unlike in the Yes-Instance solutions, if we now
consider some cluster $W_{i}$, and some random string $R\in{\mathcal{R}}$, we
may add several edges of $E(R)$ to $E_{i}$, 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 Yes-Instance solution, and thereby
obtain a more general (and hopefully more difficult) problem. But while doing
so we still need to ensure that we can prove that NDP-Grid remains at least as
hard as the newly defined problem. Recall the definition of bundles in graph
$L(H)$. It is easy to verify that in our intended solution to the Yes-
Instance, every bundle contributes at most one edge to the solution. This
motivates our definition of a slight generalization of the (r,h)-GP problem,
that we call (r,h)-Graph Partitioning Problem 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 $\tilde{G}=(V_{1},V_{2},E)$, and two integral parameters
$h,r>0$. Additionally, we are given a partition ${\mathcal{U}}_{1}$ of $V_{1}$
into groups, and a partition ${\mathcal{U}}_{2}$ of $V_{2}$ into groups, so
that for each $U\in{\mathcal{U}}_{1}\cup{\mathcal{U}}_{2}$, $|U|=r$. Using
these groups, we define bundles of edges as follows: for every vertex $v\in
V_{1}$, for each group $U\in{\mathcal{U}}_{2}$, 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\in
V_{2}$, for each group $U\in{\mathcal{U}}_{1}$, all edges that connect $v$ to
the vertices of $U$ define a bundle. We denote, for each vertex $v\in
V_{1}\cup V_{2}$, by ${\mathcal{B}}(v)$ the set of all bundles into which the
edges incident to $v$ are partitioned, and we denote by
$\beta(v)=|{\mathcal{B}}(v)|$ the number of such bundles. We also denote by
${\mathcal{B}}=\bigcup_{v\in V_{1}\cup V_{2}}{\mathcal{B}}(v)$ – the set of
all bundles. Note that as before, ${\mathcal{B}}$ is not a partition of $E$,
but every edge of $E$ belongs to exactly two bundles: one bundle in
$\bigcup_{v\in V_{1}}{\mathcal{B}}(v)$, and one bundle in $\bigcup_{v\in
V_{2}}{\mathcal{B}}(v)$. As before, we need to compute a partition
$(W_{1},\ldots,W_{r})$ of $V_{1}\cup V_{2}$ into $r$ subsets, and for each
$1\leq i\leq r$, select a subset $E_{i}\subseteq E(W_{i})$ of edges, such that
$|E_{i}|\leq h$. But now there is an additional restriction: we require that
for each $1\leq i\leq r$, for every bundle $B\in{\mathcal{B}}$, $E_{i}$
contains at most one edge $e\in B$. As before, the goal is to maximize
$\sum_{i}|E_{i}|$.

###### Valid Instances and Perfect Solutions.

Given an instance
${\mathcal{I}}=(\tilde{G}=(V_{1},V_{2},E),{\mathcal{U}}_{1},{\mathcal{U}}_{2},h,r)$
of (r,h)-GPwB, let $\beta^{*}({\mathcal{I}})=\sum_{v\in V_{1}}\beta(v)$. Note
that for any solution to ${\mathcal{I}}$, the solution value must be bounded
by $\beta^{*}({\mathcal{I}})$, since for every vertex $v\in V_{1}$, for every
bundle $B\in{\mathcal{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=\beta^{*}({\mathcal{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..

We say that instance ${\mathcal{I}}$ of (r,h)-GPwB is _valid_ iff
$h=\beta^{*}({\mathcal{I}})/r$ and $h\geq\max_{v\in V_{1}\cup
V_{2}}\left\\{\beta(v)\right\\}$.

Recall that for every group $U\in{\mathcal{U}}_{1}\cup{\mathcal{U}}_{2}$,
$|U|=r$. We now define perfect solutions to the (r,h)-GPwB problem. We will
ensure that our intended solutions in the Yes-Instance are always perfect, as
we show later.

######  Definition..

We say that a solution $((W_{1},\ldots,W_{r}),(E_{1},\ldots,E_{r}))$ to a
valid (r,h)-GPwB instance ${\mathcal{I}}$ is _perfect_ iff:

  * •

For each group $U\in{\mathcal{U}}_{1}\cup{\mathcal{U}}_{2}$, exactly one
vertex of $U$ belongs to each cluster $W_{i}$; and

  * •

For each $1\leq i\leq r$, $|E_{i}|=h$.

Note that the value of a perfect solution to a valid instance ${\mathcal{I}}$
is $h\cdot r=\beta^{*}({\mathcal{I}})$, and this is the largest value that any
solution can achieve.

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

Suppose we are given an instance $G$ of the 3COL(5) problem, and an integral
parameter $\ell>0$ (the number of repetitions). Consider the corresponding
constraint graph $H$, and suppose we are given some subgraph
$H^{\prime}\subseteq H$. We define an instance ${\mathcal{I}}(H^{\prime})$ of
(r,h)-GPwB, as follows.

  * •

The underlying graph is $L(H^{\prime})=(\hat{U}^{E},\hat{U}^{V},\hat{E})$;

  * •

The parameters are $r=6^{\ell}$ and $h=|E(H^{\prime})|$;

  * •

The partition ${\mathcal{U}}_{1}$ of $\hat{U}^{E}$ is the same as before: the
vertices of $\hat{U}^{E}$ are partitioned into groups $S(Q)$ — one group for
each query $Q\in{\mathcal{Q}}^{E}$ with $v(Q)\in V(H^{\prime})$. Similarly,
the partition ${\mathcal{U}}_{2}$ of $\hat{U}^{V}$ into groups is also defined
exactly as before, and contains, for each query
$Q^{\prime}\in{\mathcal{Q}}^{V}$ with $v(Q^{\prime})\in V(H^{\prime})$, a
group $S(Q^{\prime})$. (Recall that for all
$Q\in{\mathcal{Q}}^{E}\cup{\mathcal{Q}}^{V}$ with $v(Q)\in H^{\prime}$,
$|S(Q)|=6^{\ell}$).

######  Claim 2.3.1.

Let $G$ be an instance of the 3COL(5) problem, $\ell>0$ an integral parameter,
and $H^{\prime}\subseteq H$ a subgraph of the corresponding constraint graph.
Consider the corresponding instance ${\mathcal{I}}(H^{\prime})$ of (r,h)-GPwB.
Then ${\mathcal{I}}(H^{\prime})$ is a valid instance, and moreover, if $G$ is
a Yes-Instance, then there is a perfect solution to
${\mathcal{I}}(H^{\prime})$.

###### Proof.

We first verify that ${\mathcal{I}}(H^{\prime})$ is a valid instance of
(r,h)-GPwB. Recall that for a query $Q\in{\mathcal{Q}}^{E}$ to the edge-prover
and an answer $A\in{\mathcal{A}}^{E}$, the number of bundles incident to
vertex $v(Q,A)$ in $L(H^{\prime})$ is exactly the degree of the vertex $v(Q)$
in graph $H^{\prime}$. The total number of bundles incident to the vertices of
$S(Q)$ is then the degree of $v(Q)$ in $H^{\prime}$ times
$|{\mathcal{A}}^{E}|$. Therefore,
$\beta^{*}({\mathcal{I}})=\sum_{v(Q,A)\in\hat{U}^{E}}|\beta(v)|=|E(H^{\prime})|\cdot|{\mathcal{A}}^{E}|=h\cdot
r$. It is now immediate to verify that $h=\beta^{*}({\mathcal{I}})/r$.
Similarly, for a vertex $v=v_{j}(Q^{\prime},A^{\prime})\in U^{V}$, the number
of bundles incident to $v$ is exactly the degree of $v$ in $H^{\prime}$. Since
$h=|E(H^{\prime})|$, we get that $h\geq\max_{v\in V_{1}\cup
V_{2}}\left\\{\beta(v)\right\\}$, and so ${\mathcal{I}}(H^{\prime})$ is a
valid instance.

Assume now that $G$ is a Yes-Instance. We define a perfect solution
$((W_{1},\ldots,W_{r}),(E_{1},\ldots,E_{r}))$ to this instance. Let
$\left\\{f_{1},f_{2},\ldots,f_{6^{\ell}}\right\\}$ be the collection of
perfect global assignments of answers to the queries, given by Theorem 2.2.4.
Recall that ${\mathcal{U}}_{1}=\left\\{S(Q)\mid Q\in{\mathcal{Q}}^{E},v(Q)\in
H^{\prime}\right\\}$ and ${\mathcal{U}}_{2}=\left\\{S(Q^{\prime})\mid
Q^{\prime}\in{\mathcal{Q}}^{V},v(Q^{\prime})\in H^{\prime}\right\\}$, where
each group in ${\mathcal{U}}_{1}\cup{\mathcal{U}}_{2}$ has cardinality
$r=6^{\ell}$. We now fix some $1\leq i\leq r$, and define the set $W_{i}$ of
vertices. For each query $Q\in{\mathcal{Q}}^{E}$ to the edge-prover, if
$A=f_{i}(Q)$, then we add the vertex $v(Q,A)$ to $W_{i}$. For each query
$Q^{\prime}\in{\mathcal{Q}}^{V}$ to the vertex-prover, if
$A^{\prime}=f_{i}(Q^{\prime})$, then we select some index $1\leq j\leq
2^{\ell}$, and add the vertex $v_{j}(Q^{\prime},A^{\prime})$ to $W_{i}$. The
indices $j$ are chosen so that every vertex $v_{j}(Q^{\prime},A^{\prime})$
participates in at most one cluster $W_{i}$. From the construction of the
graph $L(H^{\prime})$ and the properties of the assignments $f_{i}$ guaranteed
by Theorem 2.2.4, it is easy to verify that $W_{1},\ldots,W_{r}$ partition the
vertices of $L(H^{\prime})$, and moreover, for each group
$S(Q)\in{\mathcal{U}}_{1}\cup{\mathcal{U}}_{2}$, each set $W_{i}$ contains
exactly one vertex of $S(Q)$.

Finally, for each $1\leq i\leq r$, we set $E_{i}=E(W_{i})$. We claim that for
each bundle $B\in{\mathcal{B}}$, set $E_{i}$ may contain at most one edge of
$B$. Indeed, let $v\in W_{i}$ be some vertex, let
$U\in{\mathcal{U}}_{1}\cup{\mathcal{U}}_{2}$ be some group, and let $B$ be the
bundle containing all edges that connect $v$ to the vertices of $U$. Since
$W_{i}$ contains exactly one vertex of $U$, at most one edge of $B$ may belong
to $E_{i}$.

It now remains to show that $|E_{i}|=h$ for all $i$. Fix some $1\leq i\leq r$.
It is easy to verify that for each random string $R=(Q,Q^{\prime})$ with
$e(R)\in H^{\prime}$, set $W_{i}$ contains a pair of vertices $v(Q,A)$,
$v_{j}(Q^{\prime},A^{\prime})$, where $A$ and $A^{\prime}$ are matching
answers to $Q$ and $Q^{\prime}$ respectively, and so the corresponding edge
connecting this pair of vertices in $L(H^{\prime})$ belongs to $E_{i}$.
Therefore, $|E_{i}|=|E(H^{\prime})|=h$.

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

The following definition will be useful for us later, when we extend our
results to NDP and EDP on wall graphs.

######  Definition..

Let ${\mathcal{P}}$ be a set of paths in a grid $\hat{G}$. We say that
${\mathcal{P}}$ is a _spaced-out_ set iff for each pair
$P,P^{\prime}\in{\mathcal{P}}$ of paths, $d(V(P),V(P^{\prime}))\geq 2$, and
all paths in ${\mathcal{P}}$ are internally disjoint from the boundaries of
the grid $\hat{G}$.

Note that if ${\mathcal{P}}$ is a set of paths that is spaced-out, then all
paths in ${\mathcal{P}}$ are mutually node-disjoint. The following theorem is
central to our hardness of approximation proof.

######  Theorem 2.3.2.

There is a constant $c^{*}>0$, and there is an efficient randomized algorithm,
that, given a valid instance
${\mathcal{I}}=(\tilde{G},{\mathcal{U}}_{1},{\mathcal{U}}_{2},h,r)$ of
(r,h)-GPwB with $|E(\tilde{G})|=M$, constructs an instance
$\hat{{\mathcal{I}}}=(\hat{G},{\mathcal{M}})$ of NDP-Grid with
$|V(\hat{G})|=O(M^{4}\log^{2}M)$, such that the following hold:

  * •

If ${\mathcal{I}}$ has a perfect solution (of value
$\beta^{*}=\beta^{*}({\mathcal{I}})$), then with probability at least
$\frac{1}{2}$ over the construction of $\hat{\mathcal{I}}$, instance
$\hat{\mathcal{I}}$ has a solution ${\mathcal{P}}$ that routes at least
$\frac{\beta^{*}}{c^{*}\log^{3}M}$ demand pairs, such that the paths in
${\mathcal{P}}$ are spaced-out; and

  * •

There is a deterministic efficient algorithm, that, given a solution
${\mathcal{P}}^{*}$ to the NDP-Grid problem instance $\hat{{\mathcal{I}}}$,
constructs a solution to the (r,h)-GPwB instance ${\mathcal{I}}$, of value at
least $\frac{|{\mathcal{P}}^{*}|}{c^{*}\cdot\log^{3}M}$.

We note that the theorem is slightly stronger than what is needed in order to
prove hardness of approximation of NDP-Grid: if ${\mathcal{I}}$ has a perfect
solution, then it is sufficient to ensure that the set ${\mathcal{P}}$ of
paths in the corresponding NDP-Grid instance $\hat{\mathcal{I}}$ is node-
disjoint. But we will use the stronger guarantee that it is spaced-out when
extending our results to NDP and EDP in wall graphs. Note that in the second
assertion we are only guaranteed that the paths in ${\mathcal{P}}^{*}$ are
node-disjoint. The proof of the theorem is somewhat technical and is deferred
to Section 2.5.

Assume now that we are given an instance $G$ of 3COL(5), an integral parameter
$\ell>0$, and a subgraph $H^{\prime}\subseteq H$ of the corresponding
constraint graph. Recall that we have constructed a corresponding instance
${\mathcal{I}}(H^{\prime})$ of (r,h)-GPwB. We can then use Theorem 2.3.2 to
construct a (random) instance of NDP-Grid, that we denote by
$\hat{{\mathcal{I}}}(H^{\prime})$. Note that $|E(L(H^{\prime}))|\leq
2^{O(\ell)}\cdot|E(H)|\leq n^{O(\ell)}$. Let $\hat{c}$ be a constant, such
that $|E(L(H^{\prime}))|\leq n^{\hat{c}\ell}$ for all $H^{\prime}\subseteq H$;
we can assume w.l.o.g. that $\hat{c}>1$. We can also assume w.l.o.g. that
$c^{*}\geq 1$, where $c^{*}$ is the constant from Theorem 2.3.2, and we denote
$c_{\mbox{{\tiny{YI}}}}=(\hat{c}\cdot c^{*})^{3}$. We obtain the following
immediate corollary of Theorem 2.3.2:

######  Corollary 2.3.3.

Suppose we are given 3COL(5) instance $G$ that is a Yes-Instance, an integer
$\ell>0$, and a subgraph $H^{\prime}\subseteq H$ of the corresponding
constraint graph. Then with probability at least $\frac{1}{2}$, instance
$\hat{{\mathcal{I}}}(H^{\prime})$ of NDP-Grid has a solution of value at least
$\frac{|E(H^{\prime})|\cdot
6^{\ell}}{c_{\mbox{{\tiny{YI}}}}\ell^{3}\log^{3}n}$, where $n=|V(G)|$. (The
probability is over the random construction of
$\hat{\mathcal{I}}(H^{\prime})$).

###### Proof.

From Claim 2.3.1, instance
${\mathcal{I}}(H^{\prime})=(L(H^{\prime}),{\mathcal{U}}_{1},{\mathcal{U}}_{2},r,h)$
of (r,h)-GPwB is a valid instance, and it has a perfect solution, whose value
must be $\beta^{*}=\beta^{*}({\mathcal{I}}(H^{\prime}))=h\cdot
r=|E(H^{\prime})|\cdot 6^{\ell}$. From Theorem 2.3.2, with probability at
least $1/2$, instance $\hat{\mathcal{I}}(H^{\prime})$ of NDP-Grid has a
solution of value at least $\frac{|E(H^{\prime})|\cdot
6^{\ell}}{c^{*}\log^{3}M}$, where $M=|E(L(H^{\prime}))|$. Since $\log
M\leq\hat{c}\ell\log n$, and the corollary follows.

###  2.4 The Hardness Proof

Let $G$ be an input instance of 3COL(5). Recall that $\gamma$ is the absolute
constant from the Parallel Repetition Theorem (Corollary 2.2.3). We will set
the value of the parameter $\ell$ later, ensuring that $\ell>\log^{2}n$, where
$n=|V(G)|$. Let $\alpha^{*}=2^{\Theta(\ell/\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 $\ell$, construct the corresponding graph $H$ (the
constraint graph), together with the graph $L(H)$. We then construct an
instance ${\mathcal{I}}(H)$ of (r,h)-GPwB as described in the previous
section, and convert it into an instance $\hat{{\mathcal{I}}}(H)$ of NDP-Grid.

We note that, if $G$ is a Yes-Instance, then from Corollary 2.3.3, with
constant probability there is a solution to $\hat{\mathcal{I}}(H)$ of value
$\frac{|{\mathcal{R}}|\cdot
6^{\ell}}{c_{\mbox{{\tiny{YI}}}}\ell^{3}\log^{3}n}$. Assume now that $G$ is a
No-Instance. If we could show that any solution to the corresponding
(r,h)-GPwB instance ${\mathcal{I}}(H)$ has value less than
$\frac{|{\mathcal{R}}|\cdot
6^{\ell}}{c_{\mbox{{\tiny{YI}}}}^{2}\cdot\alpha^{*}\ell^{6}\log^{6}n}$, we
would be done. Indeed, in such a case, from Theorem 2.3.2, every solution to
the NDP-Grid instance $\hat{\mathcal{I}}(H)$ routes fewer than
$\frac{|{\mathcal{R}}|\cdot
6^{\ell}}{c_{\mbox{{\tiny{YI}}}}\alpha^{*}\ell^{3}\log^{3}n}$ demand pairs. If
we assume for contradiction that an $\alpha^{*}$-approximation algorithm
exists for NDP-Grid, then, if $G$ is a Yes-Instance, the algorithm would have
to return a solution to $\hat{\mathcal{I}}(H)$ routing at least
$\frac{|{\mathcal{R}}|\cdot
6^{\ell}}{c_{\mbox{{\tiny{YI}}}}\alpha^{*}\ell^{3}\log^{3}n}$ demand pairs,
while, if $G$ is a No-Instance, no such solution would exist. Therefore, we
could use the $\alpha^{*}$-approximation algorithm for NDP-Grid to distinguish
between the Yes-Instances and the No-Instances of 3COL(5).

Unfortunately, we are unable to prove this directly. Our intended solution to
the (r,h)-GPwB instance ${\mathcal{I}}(H)$, defined over the graph $L(H)$, for
each query $Q\in{\mathcal{Q}}^{E}\cup{\mathcal{Q}}^{V}$, places every vertex
of $S(Q)$ into a distinct cluster. Any such solution will indeed have a low
value in the No-Instance. But a cheating solution may place many vertices from
the same set $S(Q)$ into some cluster $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_{i}$. The main idea in our reduction is to overcome this difficulty
by noting that such a cheating solution can be used to compute a partition of
the constraint graph $H$. The graph is partitioned into as many as $6^{\ell}$
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\in{\mathcal{R}}$, whose corresponding edges have
survived the partitioning procedure, then the problem does not become
significantly easier, and we can recursively apply the same argument to the
resulting subgraphs of $H$. We make a significant progress in each such
iteration, since the sizes of the resulting sub-graphs of $H$ decrease very
fast. The main tool that allows us to execute this plan is the following
theorem.

######  Theorem 2.4.1.

Suppose we are given an instance $G$ of the 3COL(5) problem with $|V(G)|=n$,
and an integral parameter $\ell>\log^{2}n$, together with some subgraph
$H^{\prime}\subseteq H$ of the corresponding constraint graph $H$, and a
parameter $P>1$. Consider the corresponding instance
${\mathcal{I}}(H^{\prime})$ of (r,h)-GPwB, and assume that we are given a
solution to this instance of value at least $|E(H^{\prime})|\cdot
6^{\ell}/\alpha$, where
$\alpha=c_{\mbox{{\tiny{YI}}}}^{2}\cdot\alpha^{*}\cdot\ell^{6}\log^{6}n$. Then
there is a randomized algorithm whose running time is
$O\left(n^{O(\ell)}\cdot\log P\right)$, that returns one of the following:

  * •

Either a randomized strategy for the two provers that satisfies, in
expectation, more than a $2^{-\gamma\ell/2}$-fraction of the constraints
$R\in{\mathcal{R}}$ with $e(R)\in E(H^{\prime})$; or

  * •

A collection ${\mathcal{H}}$ of disjoint sub-graphs of $H^{\prime}$, such that
for each $H^{\prime\prime}\in{\mathcal{H}}$,
$|E(H^{\prime\prime})|\leq|E(H^{\prime})|/2^{\gamma\ell/16}$, and with
probability at least $(1-1/P)$,
$\sum_{H^{\prime\prime}\in{\mathcal{H}}}|E(H^{\prime\prime})|\geq\frac{c^{\prime}|E(H^{\prime})|}{\ell^{2}\alpha^{2}}$,
for some universal constant $c^{\prime}$.

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-$\alpha^{*}$ approximation algorithm ${\mathcal{A}}$ for
NDP-Grid (recall that $\alpha^{*}=2^{\Theta(\ell/\log n)}$). We will use this
algorithm to distinguish between the Yes-Instances and the No-Instances of
3COL(5). Suppose we are given an instance $G$ of 3COL(5).

For an integral parameter $\ell>\log^{2}n$, let $H$ be the constraint graph
corresponding to $G$ and $\ell$. We next show a randomized algorithm, that
uses ${\mathcal{A}}$ as a subroutine, in order to determine whether $G$ is a
Yes-Instance or a No-Instance. The running time of the algorithm is
$n^{O(\ell)}$.

Throughout the algorithm, we maintain a collection ${\mathcal{H}}$ of sub-
graphs of $H$, that we sometimes call clusters. Set ${\mathcal{H}}$ is in turn
partitioned into two subsets: set ${\mathcal{H}}_{1}$ of active clusters, and
set ${\mathcal{H}}_{2}$ of inactive clusters. Consider now some inactive
cluster $H^{\prime}\in{\mathcal{H}}_{2}$. This cluster defines a $2$-prover
game ${\mathcal{G}}(H^{\prime})$, where the queries to the two provers are
$\left\\{Q^{E}\in{\mathcal{Q}}^{E}\mid v(Q^{E})\in V(H^{\prime})\right\\}$,
and $\left\\{Q^{V}\in{\mathcal{Q}}^{V}\mid v(Q^{V})\in V(H^{\prime})\right\\}$
respectively, and the constraints of the verifier are
${\mathcal{R}}(H^{\prime})=\left\\{R\in{\mathcal{R}}\mid e(R)\in
E(H^{\prime})\right\\}$. For each inactive cluster
$H^{\prime}\in{\mathcal{H}}_{2}$, we will store a (possibly randomized)
strategy of the two provers for game ${\mathcal{G}}(H^{\prime})$, that
satisfies at least a $2^{-\gamma\ell/2}$-fraction of the constraints in
${\mathcal{R}}(H^{\prime})$.

At the beginning, ${\mathcal{H}}$ contains a single cluster – the graph $H$,
which is active. The algorithm is executed while
${\mathcal{H}}_{1}\neq\emptyset$, and its execution is partitioned into
phases. In every phase, we process each of the clusters that belongs to
${\mathcal{H}}_{1}$ 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^{\prime}\in{\mathcal{H}}_{1}$. We describe an iteration when
an active cluster $H^{\prime}\in{\mathcal{H}}_{1}$ is processed in Figure 2.2
(see also the flowchart in Figure 2.3).

If the algorithm terminates with ${\mathcal{H}}$ containing only inactive
clusters, then we return “$G$ is a Yes-Instance”.

###### Correctness.

We establish the correctness of the algorithm in the following two lemmas.

######  Lemma 2.4.2.

If $G$ is a Yes-Instance, then with high probability, the algorithm returns
“$G$ is a Yes-Instance”.

###### Proof.

Consider an iteration of the algorithm when an active cluster $H^{\prime}$ is
processed. Notice that the algorithm may only determine that $G$ is a No-
Instance in Item 3 or in Item 5b. We now analyze these two steps.

Consider first Item 3. From Corollary 2.3.3, with probability at least $1/2$,
a random graph $\hat{\mathcal{I}}(H^{\prime})$ has a solution of value at
least $\frac{|E(H^{\prime})|\cdot
6^{\ell}}{c_{\mbox{{\tiny{YI}}}}\ell^{3}\log^{3}n}$, and our
$\alpha^{*}$-approximation algorithm to NDP-Grid must then return a solution
of value at least $\frac{|E(H^{\prime})|\cdot
6^{\ell}}{c_{\mbox{{\tiny{YI}}}}\alpha^{*}\ell^{3}\log^{3}n}$ . Since we use
$n^{4\ell}$ independent random constructions of
$\hat{\mathcal{I}}(H^{\prime})$, with high probability, for at least one of
them, we will obtain a solution of value at least
$\frac{|E(H^{\prime})|6^{\ell}}{c_{\mbox{{\tiny{YI}}}}\alpha^{*}\ell^{3}\log^{3}n}$.
Therefore, with high probability our algorithm will not return “$G$ is a No-
Instance” due to Item 3 in this iteration.

Consider now Item 5b. The algorithm can classify $G$ as a No-Instance in this
step only if
$\sum_{H^{\prime\prime}\in{\mathcal{H}}}|E(H^{\prime\prime})|<\frac{c^{\prime}|E(H^{\prime})|}{\ell^{2}\alpha^{2}}$.
From Theorem 2.4.1, this happens with probability at most $1/P$, and from our
setting of the parameter $P$ to be $n^{c\ell}$ for a large enough constant
$c$, with high probability our algorithm will not return “$G$ is a No-
Instance” due to Item 5b in this iteration.

It is not hard to see that our algorithm performs $n^{O(\ell)}$ iterations,
and so, using the union bound, with high probability, it will classify $G$ as
a Yes-Instance.

Iteration for Processing a Cluster $H^{\prime}\in{\mathcal{H}}_{1}$ 1.
Construct an instance ${\mathcal{I}}(H^{\prime})$ of (r,h)-GPwB. 2. Use
Theorem 2.3.2 to independently construct $n^{4\ell}$ instances
$\hat{{\mathcal{I}}}(H^{\prime})$ of the NDP-Grid problem. 3. Run the
$\alpha^{*}$-approximation algorithm ${\mathcal{A}}$ on each such instance
$\hat{{\mathcal{I}}}(H^{\prime})$. If the resulting solution, for each of
these instances, routes fewer than
$\frac{|E(H^{\prime})|6^{\ell}}{c_{\mbox{{\tiny{YI}}}}\alpha^{*}\ell^{3}\log^{3}n}$
demand pairs, halt and return “$G$ is a No-Instance”. 4. Otherwise, fix any
instance $\hat{\mathcal{I}}(H^{\prime})$ for which the algorithm returned a
solution routing at least
$\frac{|E(H^{\prime})|6^{\ell}}{c_{\mbox{{\tiny{YI}}}}\alpha^{*}\ell^{3}\log^{3}n}$
demand pairs. Denote $|E(L(H^{\prime}))|=M$, and recall that $M\leq
n^{\hat{c}\ell}$. Use Theorem 2.3.2 to compute a solution
$((W_{1},\ldots,W_{r}),(E_{1},\ldots,E_{r}))$ to the instance
${\mathcal{I}}(H^{\prime})$ of the (r,h)-GPwB problem, of value at least:
$\frac{|E(H^{\prime})|\cdot
6^{\ell}}{(c_{\mbox{{\tiny{YI}}}}\alpha^{*}\ell^{3}\log^{3}n)(c^{*}\log^{3}M)}\geq\frac{|E(H^{\prime})|\cdot
6^{\ell}}{c_{\mbox{{\tiny{YI}}}}c^{*}\hat{c}^{3}\alpha^{*}\ell^{6}\log^{6}n}\geq\frac{|E(H^{\prime})|\cdot
6^{\ell}}{c_{\mbox{{\tiny{YI}}}}^{2}\alpha^{*}\ell^{6}\log^{6}n}=\frac{|E(H^{\prime})|\cdot
6^{\ell}}{\alpha}.$ 5. Apply the algorithm from Theorem 2.4.1 to this
solution, with the parameter $P=n^{c\ell}$, for a sufficiently large constant
$c$. (a) If the outcome is a strategy for the provers satisfying more than a
$2^{-\gamma\ell/2}$-fraction of constraints $R\in{\mathcal{R}}$ with $e(R)\in
E(H^{\prime})$, then declare cluster $H^{\prime}$ inactive and move it from
${\mathcal{H}}_{1}$ to ${\mathcal{H}}_{2}$. Store the resulting strategy of
the provers. (b) Otherwise, let $\tilde{\mathcal{H}}$ be the collection of
sub-graphs of $H^{\prime}$ returned by the algorithm. If
$\sum_{H^{\prime\prime}\in{\mathcal{H}}}|E(H^{\prime\prime})|<\frac{c^{\prime}|E(H^{\prime})|}{\ell^{2}\alpha^{2}}$,
then return “$G$ is a No-Instance”. Otherwise, remove $H^{\prime}$ from
${\mathcal{H}}_{1}$ and add all graphs of $\tilde{\mathcal{H}}$ to
${\mathcal{H}}_{1}$.

Figure 2.2: An iteration description of the algorithm of Theorem 2.1.1 Figure
2.3: Flowchart for an iteration execution of the algorithm of Theorem 2.1.1

######  Lemma 2.4.3.

If $G$ is a No-Instance, then the algorithm always returns “$G$ is a No-
Instance”.

###### Proof.

From Corollary 2.2.3, it is enough to show that, whenever the algorithm
classifies $G$ as a Yes-Instance, there is a strategy for the two provers,
that satisfies more than a fraction-$2^{-\gamma\ell}$ of the constraints in
${\mathcal{R}}$.

Note that the original graph $H$ has at most $n^{\hat{c}\ell}$ edges. In every
phase, the number of edges in each active graph decreases by a factor of at
least $2^{\gamma\ell/16}$. Therefore, the number of phases is bounded by
$O(\log n)$. If the algorithm classifies $G$ as a Yes-Instance, then it must
terminate when no active clusters remain. In every phase, the number of edges
in $\bigcup_{H^{\prime}\in{\mathcal{H}}}E(H^{\prime})$ goes down by at most a
factor $\ell^{2}\alpha^{2}/c^{\prime}$. Therefore, at the end of the
algorithm:

$\sum_{H^{\prime}\in{\mathcal{H}}_{2}}|E(H^{\prime})|\geq\frac{|{\mathcal{R}}|}{(\ell^{2}\alpha^{2}/c^{\prime})^{O(\log
n)}}=\frac{|{\mathcal{R}}|}{(\ell^{14}\cdot(\alpha^{*})^{2}\cdot\log^{12}n)^{O(\log
n)}}=\frac{|{\mathcal{R}}|}{(\alpha^{*})^{O(\log n)}}.$

By appropriately setting $\alpha^{*}=2^{\Theta(\ell/\log n)}$, we will ensure
that the number of edges remaining in the inactive clusters
$H^{\prime}\in{\mathcal{H}}_{2}$ is at least
$|{\mathcal{R}}|/2^{\gamma\ell/4}$. Each such edge corresponds to a distinct
random string $R\in{\mathcal{R}}$. Recall that for each inactive cluster
$H^{\prime}$, there is a strategy for the provers in the corresponding game
${\mathcal{G}}(H^{\prime})$ that satisfies at least
$|E(H^{\prime})|/2^{\gamma\ell/2}$ of its constraints. Taking the union of all
these strategies, we can satisfy more than $|{\mathcal{R}}|/2^{\gamma\ell}$
constraints of ${\mathcal{R}}$, contradicting the fact that $G$ is a No-
Instance.

###### Running Time and the Hardness Factor.

As observed above, our algorithm has at most $n^{O(\ell)}$ iterations, where
in every iteration it processes a distinct active cluster $H^{\prime}\subseteq
H$. The corresponding graph $L(H^{\prime})$ has at most $n^{O(\ell)}$ edges,
and so each of the $n^{O(\ell)}$ resulting instances of NDP-Grid contains at
most $n^{O(\ell)}$ vertices. Therefore, the overall running time of the
algorithm is $n^{O(\ell)}$. From the above analysis, if $G$ is a No-Instance,
then the algorithm always classifies it as such, and if $G$ is a Yes-Instance,
then the algorithm classifies it as a Yes-Instance with high probability. The
hardness factor that we obtain is $\alpha^{*}=2^{\Theta(\ell/\log n)}$, while
we only apply our approximation algorithm to instances of NDP-Grid containing
at most $N=n^{O(\ell)}$ vertices. The running time of the algorithm is
$n^{O(\ell)}$, and it is a randomized algorithm with a one-sided error.

Setting $\ell=\log^{p}n$ for a large enough integer $p$, we obtain
$\alpha^{*}=2^{\Theta((\log N)^{1-2/(p+1)})}$, giving us a $2^{(\log
n)^{(1-\epsilon)}}$-hardness of approximation for NDP-Grid for any constant
$\epsilon$, assuming $\mbox{\sf NP}\not\subseteq\mbox{\sf
RTIME}(n^{\operatorname{poly}\log n})$.

Setting $\ell=n^{\delta}$ for some constant $\delta$, we get that
$N=2^{O(n^{\delta}\log n)}$ and $\alpha^{*}=2^{\Theta(n^{\delta}/\log n)}$,
giving us a $n^{\Omega(1/(\log\log n)^{2})}$-hardness of approximation for
NDP-Grid, assuming that $\mbox{\sf NP}\not\subseteq\mbox{\sf
RTIME}(2^{n^{\delta}})$ for some constant $\delta>0$.

####  2.4.1 Prover Strategy or Partition — Proof of Theorem 2.4.1

Recall that each edge of graph $H^{\prime}$ corresponds to some constraint