Authors Rahul Jain, Raghunath Tewari,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23
www.theoryofcomputing.org
On Solving Reachability in Grid Digraphs
using a Pseudoseparator
Rahul Jain Raghunath Tewari
Received January 13, 2020; Revised May 25, 2022; Published August 28, 2023
Abstract. The reachability problem asks to decide if there exists a path from one
vertex to another in a digraph. In a grid digraph, the vertices are the points of
a two-dimensional square grid, and an edge can occur between a vertex and its
immediate horizontal and vertical neighbors only.
Asano and Doerr (CCCGβ11) presented the first simultaneous time-space bound
for reachability in grid digraphs by solving the problem in polynomial time and
Λ 1/3 ) by Ashida
π(π 1/2+π ) space. In 2018, the space complexity was improved to π(π
and Nakagawa (SoCGβ18).
In this paper, we show that there exists a polynomial-time algorithm that uses
π(π 1/4+π ) space to solve the reachability problem in a grid digraph containing π
vertices. We define and construct a new separator-like device called pseudoseparator
to develop a divide-and-conquer algorithm. This algorithm works in a space-efficient
manner to solve reachability.
A conference version of this paper appeared in the Proceedings of the 39th IARCS Annual Conference on
Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) [10].
ACM Classification: G.2.2
AMS Classification: 68Q25
Key words and phrases: digraph reachability, grid digraph, graph algorithm, sublinear space
algorithm
Β© 2023 Rahul Jain and Raghunath Tewari
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2023.v019.a002
R AHUL JAIN AND R AGHUNATH T EWARI
1 Introduction
Let π and π‘ be vertices of a given directed graph (digraph). The problem of digraph reachability
is to decide if there is a path from π to π‘. This problem has many applications in the field
of algorithms and computational complexity theory. Many algorithms for network-related
problems use it as a subroutine. Digraph reachability is NL-complete and thus captures the
complexity of nondeterministic logarithmic space. Hence designing better algorithms for this
problem is of utmost importance to the theory of computing.
Standard traversal algorithms such as DFS and BFS give a linear-time algorithm for this prob-
lem, but they require linear space. Savitchβs divide-and-conquer algorithm solves reachability
in π(log2 π) space. However, as a tradeoff, it requires π π(log π) time [14]. Hence it is natural to
ask whether we can get the best of both worlds and design an algorithm for digraph reachability
that runs in polynomial time and uses polylogarithmic space. Wigderson asked a relaxed version
of this question in his survey, whether digraph reachability can be solved by a polynomial-time
algorithm that uses π(π 1βπ ) space [16].
β
Barnes et al. showed that digraph reachability can be decided simultaneously in π/2Ξ( log π)
space and polynomial time [6]. Although this algorithm gives a sublinear space bound, it still
does not answer Wigdersonβs question.
Undirected graphs can be considered as a specific type of digraphs, where adjacency is a
symmetric relation. Reachability in undirected graphs can be solved in logspace [13]. Also, for
certain classes of digraphs, where the underlying undirected graph is topologically restricted,
we know of polynomial time algorithms with space complexity better than linear. Imai et
al. presented a polynomial-time algorithm that solves reachability for planar digraphs using
π(π 1/2+π ) space for any π > 0 [9]. Later, Asano et al. presented a polynomial-time algorithm
whose space complexity was π(π Λ 1/2 ) for the same problem [4]. For digraphs of higher genus,
Chakraborty et al. presented a polynomial-time algorithm that uses π(π Λ 2/3 π 1/3 ) space. Their
algorithm additionally requires an embedding of the underlying undirected graph on a surface
Λ 2/3 )-space algorithm for π»-minor-free
of genus π, as part of the input [7]. They also gave an π(π
digraphs which requires a tree decomposition of the underlying undirected graph as part of
the input and π(π 1/2+π )-space algorithms for πΎ 3,3 -minor-free digraphs and for πΎ 5 -minor-free
digraphs.
For layered planar digraphs Chakraborty and Tewari showed that for every π > 0, there is an
π(π π )-space algorithm [8]. Stolee and Vinodchandran presented a polynomial-time algorithm
that, for any π > 0 solves reachability in an acyclic digraph with π(π π ) sources and embedded
on the surface of genus π(π π ) using π(π π ) space [15]. For unique-path digraphs Kannan et al.
presented an π(π π )-space, polynomial-time algorithm [11].
In this paper, grid digraphs are our concern. Grid digraphs are a subclass of planar digraphs.
In a grid digraph, the vertices are the points of an π Γ π grid. The edges can only occur between
a vertex and its immediate vertical and horizontal neighbours. We know that reachability in
planar digraphs can be reduced to reachability in grid digraphs in logarithmic space [1]. The
reduction, however, causes at least a quadratic blow-up in the size of the digraph. In this paper,
we study the simultaneous timeβspace complexity of reachability in grid graphs.
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 2
O N S OLVING R EACHABILITY IN G RID D IGRAPHS U SING A P SEUDOSEPARATOR
Asano and Doerr presented a polynomial-time algorithm that uses π(π 1/2+π ) space for
solving reachability in grid digraphs [3]. Ashida and Nakagawa presented an algorithm with
improved space complexity of π(π e 1/3 ) [5]. The latter algorithm proceeds by first dividing
the input grid digraph into subgrids. It then uses a gadget to transform each subgrid into a
planar digraph, making the whole of the resultant digraph planar. Finally, it uses the planar
reachability algorithm of Imai et al. [9] as a subroutine to get the desired space bound.
In this paper, we present a π(π 1/4+π ) space and polynomial-time algorithm for grid digraph
reachability, thereby significantly improving the space bound of Ashida and Nakagawa.
Theorem 1.1 (Main Theorem). For every π > 0, there exists a polynomial-time algorithm that solves
reachability in an π-vertex grid digraph using π(π 1/4+π ) space.
The approach of Ashida and Nakagawa [5] is to reduce the size of the input π-vertex digraph
to a digraph of size π(π 2/3 ). Their new graph preserves reachability between vertices and is
planar. They use the planar-reachability algorithm of Asano et al. [4]. Our approach is slightly
different. We convert the input digraph into an auxiliary digraph of size π(π 1/2+πΌ/2 ) for arbitrarily
small πΌ. The auxiliary digraph is created by dividing the given grid digraph into subgrids and
replacing paths in each subgrid with a single edge between the boundary vertices. While our
auxiliary digraph preserves reachability, it is not planar; and hence we cannot use Asano et
al.βs algorithm directly. The auxiliary digraph comes with a drawing with the crossing property,
that is, if two edges, π and π , cross each other in this drawing, there necessarily exist two more
edges, one from the tail of π to the head of π and the other from the tail of π to the head of
π, in the digraph. This property allows us to use a device that we call pseudoseparator to solve
reachability in it. A pseudoseparator designates a set of vertices, a set of edges and a set of
components of the digraph, such that a path from one component to another necessarily either
takes a vertex of the pseudoseparator or crosses one of the edges of the pseudoseparator in the
drawing. We finally solve the problem by recursively solving each of these components and
using a traversal algorithm. Due to the crossing property, we are required to store only a small
number of vertices for performing the traversal, thereby saving space.
In Section 2, we state the definitions and notation that we use in this paper. In Section 3, we
define the auxiliary digraph and state various properties of it that we use later. In Section 4,
we discuss the concept of the pseudoseparator. We give its formal definition and show how to
compute the pseudoseparator efficiently. In Section 5, we give the algorithm to solve reachability
in an auxiliary digraph and prove its correctness. Finally in Section 6 we use the algorithm of
Section 5 to give an algorithm to decide reachability in grid digraphs and thus prove Theorem 1.1.
2 Preliminaries
Let [π] denote the set {0, 1, 2, . . . , π}. We denote the vertex set of a digraph πΊ by π(πΊ) and its
edge set by πΈ(πΊ). We assume that the vertices of a digraph are indexed by integers from 1 to
|π(πΊ)|. For a subset π of π(πΊ), we denote the sub-digraph of πΊ induced by the vertices of π
as πΊ[π] and we denote the sub-digraph of πΊ induced by the vertices π(πΊ) \ π as πΊ \ π. For
a digraph πΊ, we write cc(πΊ) to denote the set of all connected components in the underlying
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 3
R AHUL JAIN AND R AGHUNATH T EWARI
undirected graph of πΊ. By the underlying undirected graph, we mean the graph formed by
symmetrizing the adjacency relation. To do this, we consider each directed edge in the digraph
and create an undirected edge between the corresponding vertices. Henceforth, whenever we
talk about connected components, we will mean the connected components of the underlying
undirected graph. In a drawing of a graph in the plane we map each vertex to a point in the plane
and each edge to a simple arc whose endpoints coincide with the images of the end vertices of
the edge. Moreover, the image of a vertex does not belong to the interior of an arc corresponding
to any edge. We say that a graph is planar if there exists a drawing of that graph on a plane such
that no two arcs corresponding to the edges of the graph intersect except at the endpoints. Such
a drawing is called a planar embedding.
A planar digraph is a digraph whose underlying undirected graph is planar. Similarly, a
drawing of a digraph is defined as the drawing of its underlying undirected graph.
We will represent a planar graph by describing the cyclic ordering of a graphβs edges around
each vertex. We note that the results in [2] and [13] combine to a deterministic logarithmic space
algorithm that decides whether a given graph is planar, and if it is, outputs a planar embedding.
Hence, when dealing with planar graphs, we will assume without loss of generality that we
have a planar embedding whenever required. An π Γ π grid digraph is a directed graph whose
set of vertices is [π] Γ [π] = {0, 1, . . . , π} Γ {0, 1, . . . , π} so that if ((π1 , π1 ), (π2 , π2 )) is an edge
then |π1 β π2 | + | π1 β π2 | = 1. In other words, we start with an undirected π Γ π grid graph. Then,
we remove some of the edges and assign directions to the remaining edges while keeping all the
vertices. This process results in the formation of an π Γ π grid digraph, which has a total of
π = (π + 1)2 vertices. It follows from the definition that grid digraphs are planar.
We will work with π Γ π grid digraphs where π = π(π 1/2 ). Hence, a space complexity of
0
π(π 1/2+π ) will translate into a space complexity of π(π 1/4+π ) as required.
3 Auxiliary graph
Let πΊ be an π Γ π grid digraph. We divide πΊ into π 2πΌ subgrids such that each subgrid is a
π 1βπΌ Γ π 1βπΌ grid. Formally, for 0 < πΌ < 1 and 1 β€ π, π β€ π πΌ , the (π, π)-th subgrid of πΊ, denoted
πΊ[π, π], is the sub-digraph of πΊ induced by the set of vertices, π(πΊ[π, π]), where π(πΊ[π, π]) is
{(π 0 , π 0) | (π β 1) Β· π 1βπΌ β€ π 0 β€ π Β· π 1βπΌ and (π β 1) Β· π 1βπΌ β€ π 0 β€ π Β· π 1βπΌ } .
For ease of presentation, we will assume without loss of generality that variables like π and
πΌ are such that the values like π πΌ and π 1βπΌ are integers.
We define the auxiliary digraph AuxπΌ (πΊ)[π, π] as follows. The vertex set of AuxπΌ (πΊ)[π, π] is
the set of vertices on the boundary of πΊ[π, π]. That means, π(AuxπΌ (πΊ)[π, π]) is
{(π 0 , π 0) | (π 0 , π 0) β π(πΊ[π, π]) and
((π β 1) Β· π 1βπΌ = π 0 or π Β· π 1βπΌ = π 0 or (π β 1) Β· π 1βπΌ = π 0 or π Β· π 1βπΌ = π 0)} .
For two vertices π’, π£ in AuxπΌ (πΊ)[π, π], (π’, π£) is an edge in AuxπΌ (πΊ)[π, π] if there is a path from π’ to
π£ in the subgrid πΊ[π, π]. We draw AuxπΌ (πΊ)[π, π] on an Euclidean plane by mapping vertex (π₯, π¦)
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 4
O N S OLVING R EACHABILITY IN G RID D IGRAPHS U SING A P SEUDOSEPARATOR
to the point with coordinates (π₯, π¦). The points corresponding to vertices of AuxπΌ (πΊ)[π, π] thus
lie on a square. We use a straight line segment to represent the edge if π’ and π£ do not lie on a
single side of this square. and an arc inside the square to represent it otherwise.
We define the πΌ-auxiliary digraph, AuxπΌ (πΊ) as follows. The vertex set of AuxπΌ (πΊ), π(AuxπΌ (πΊ)) =
{(π, π) | π = π Β· π 1βπΌ or π = π Β· π 1βπΌ , such that 0 β€ π, π β€ π πΌ }. The edges of AuxπΌ (πΊ) are the edges
of AuxπΌ (πΊ)[π, π] taken over all pairs (π, π). Note that AuxπΌ (πΊ) might have parallel edges, since an
edge on a side of a block might be in the adjacent block as well. In such cases we preserve both
the edges, in their different blocks of AuxπΌ (πΊ) in the drawing of AuxπΌ (πΊ) on the plane. Figure 1
contains an example of a grid digraph partitioned into subgrids and its corresponding auxiliary
digraph. Since each block AuxπΌ (πΊ)[π, π] contains 4π 1βπΌ vertices, the total number of vertices in
AuxπΌ (πΊ) is at most 4π 1+πΌ .
Our algorithm for reachability first constructs AuxπΌ (πΊ) by solving each of the π 1βπΌ Γ π 1βπΌ
grids recursively. It then uses a polynomial-time subroutine to decide reachability in AuxπΌ (πΊ).
Note that we do not store the digraph AuxπΌ (πΊ) explicitly since that would require too much
space. Rather we solve a subgrid recursively whenever the subroutine queries for an edge in
that subgrid of AuxπΌ (πΊ).
Our strategy is to develop a polynomial-time algorithm which solves reachability in AuxπΌ (πΊ)
using π( Λ πΛ 1/2+π½/2 ) space where π Λ is the number of vertices in AuxπΌ (πΊ). As discussed earlier, π Λ
is at most 4π 1+πΌ . Hence, the main algorithm requires π(π Λ 1/2+π½/2+πΌ/2+πΌπ½/2 ) space. For a fixed
constant π > 0, we can pick πΌ > 0 and π½ > 0 such that the space complexity becomes π(π 1/2+π ).
Figure 1: A grid digraph πΊ divided into subgrids and its corresponding auxiliary digraph
AuxπΌ (πΊ)
3.1 Properties of the auxiliary digraph
In the following definition, we give ordered labelling to the vertices of a block of the auxiliary
digraph. We define the labelling with respect to some vertex in the block.
Definition 3.1. Let πΊ be a π Γ π grid digraph, β = AuxπΌ (πΊ)[π, π] be a block of AuxπΌ (πΊ) and
π£ = (π₯, π¦) be a vertex in AuxπΌ (πΊ)[π, π]. Let π‘ = π 1βπΌ . We define a cyclic permutation πβ on the
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 5
R AHUL JAIN AND R AGHUNATH T EWARI
vertex set of AuxπΌ (πΊ)[π, π] as follows:
ο£±

 (π₯ + 1, π¦) if π₯ < (π + 1)π‘ and π¦ = ππ‘
(π₯, π¦ + 1) if π₯ = (π + 1)π‘ and π¦ < (π + 1)π‘


ο£²

π π (π£) =

 (π₯ β 1, π¦) if π₯ > ππ‘ and π¦ = (π + 1)π‘

 (π₯, π¦ β 1)

if π₯ = ππ‘ and π¦ > ππ‘
ο£³
For any non-negative integer π, we define πβπ inductively as follows. For π = 0, π ππ (π£) = π£ and
otherwise we have π ππ+1 (π£) = π π (π ππ (π£)).
Note that the permutation πβ can be seen as a counter-clockwise shift. Also note that for
π
a block β and vertices π£ and π€ in it, we can write π£ as π π (π€) where π is smallest non-negative
π
integer for which π π (π€) = π£. Next we formalize what it means to say that two edges of the
auxiliary digraph cross each other.
Definition 3.2. Let πΊ be a grid digraph and β be a block of AuxπΌ (πΊ). For two distinct edges π
π π
and π in the block, such that π = (π£, π π (π£)) and π = (π π (π£), π ππ (π£)). We say that edges π and π
cross each other if min(π, π) < π < max(π, π).
Note the definition of cross given above is symmetric. That is, if edges π and π cross each
π
other then π and π must cross each other as well. For an edge π = (π π (π£), π ππ (π£)), we define
ββ π
π = (π ππ (π£), π π (π£)) and call it the reverse of π . We also note that if π and π cross each other, then π
ββ
and π also cross each other.
In Lemma 3.3 we state an equivalent condition of the crossing of two edges. In Lemmas 3.5
and 3.6 we state some specific properties of the auxiliary digraph that we use later.
Lemma 3.3. Let πΊ be a grid digraph and β be a block of AuxπΌ (πΊ). Let π€ be an arbitrary vertex in the
π π
block β and π = (π π (π€), π π (π€)) and π = (π ππ (π€), π ππ (π€)) be two distinct edges in β . Then π and π cross
each other if and only if either of the following two conditions hold:
β’ min(π, π) < min(π, π ) < max(π, π) < max(π, π )
β’ min(π, π ) < min(π, π) < max(π, π ) < max(π, π)
Proof. We prove that if min(π, π) < min(π, π ) < max(π, π) < max(π, π ) then π and π cross each
other. We let π < π < π < π . Other cases can be proved by reversing appropriate edges.
We thus have integers π1 = π β π, π1 = π β π and π 1 = π β π. Clearly, π1 < π1 < π 1 . Let
π π π π π
π£ = π π (π€). Thus we have π = (π£, π π (π€)) = (π£, π π 1 (π π (π€))) = (π£, π π 1 (π£)) and π = (π ππ (π€), π ππ (π€)) =
π π
(π ππ1 (π π (π€)), π ππ 1 (π π (π€))) = (π ππ1 (π£), π ππ 1 (π£)) The proof for the second condition is similar.
π π
Now, we prove that if π = (π π (π€), π π (π€)) and π = (π ππ (π€), π ππ (π€)) cross each other then either of
the given two condition holds. We assume that π is the smallest integer among π, π, π and π . Other
π
cases can be proved similarly. Now, let π£ = π π (π€). We thus have integers π 1 = π β π, π1 = π β π
π1
and π 1 = π β π such that π = (π£, π π (π£)) and π = (π ππ1 (π£), π ππ 1 (π£)). Since π and π cross each other,
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 6
O N S OLVING R EACHABILITY IN G RID D IGRAPHS U SING A P SEUDOSEPARATOR
we have min(π1 , π 1 ) < π1 < max(π1 , π 1 ). Thus min(π1 + π, π 1 + π) < π1 + π < max(π1 + π, π 1 + π).
It follows that min(π, π ) < π < max(π, π ). Since we assumed π to be smallest integer among π, π,
π and π ; we have min(π, π) < min(π, π ) < max(π, π) < max(π, π ), thus proving the lemma.
We see that we can draw an auxiliary digraph on a plane such that the arcs corresponding to
two of its edges intersect if and only if the corresponding edges cross each other. Henceforth,
we will work with such a drawing.
Definition 3.4. Let πΊ be a grid digraph and β be a block of AuxπΌ (πΊ). For a vertex π£ and edges
π
π , π such that π = (π π (π£), π ππ (π£)) and π = (π ππ (π£), π ππ‘ (π£)), we say that π is closer to π£ than π if
min(π, π) < min(π , π‘).
We say π is closest to π£ if there exists no other edge π 0 which is closer to π£ than π .
Lemma 3.5. Let πΊ be a grid digraph and π1 = (π’1 , π£1 ) and π2 = (π’2 , π£2 ) be two edges in AuxπΌ (πΊ). If π1
and π2 cross each other, then AuxπΌ (πΊ) also contains the edges (π’1 , π£2 ) and (π’2 , π£1 ).
π π
Proof. Let π1 = (π£, π π (π£)) and π2 = (π π (π£), π ππ (π£)) be two edges that cross each other in AuxπΌ (πΊ).
Let β be the block of AuxπΌ (πΊ) to which π1 and π2 belong. Consider the subgrid of πΊ which is
solved to construct the block β . Since the edge π1 exists in block β , there exists a path π from π£ to
π
π π (π£) in the underlying subgrid. This path π divides the subgrid into two parts such that the
π π
vertices π π (π£) and π ππ (π£) belong to different parts of the subgrid. Thus, a path between π π (π£) and
π ππ (π£) necessarly take a vertex of path π. Hence, there is a path from π£ to π ππ (π£) and a path from
π
π π (π£) to π ππ (π£). Thus the lemma follows.
Figure 2: Edge crossings in an auxiliary grid. On the left, there is one block of the auxiliary
digraph that contains edges that cross. The dotted edges are the ones whose existence is made
necessary by Lemma 3.5. On the right, a subgrid which results in the auxiliary block on the left.
Lemma 3.6. Let πΊ be a grid digraph and π1 = (π’1 , π£1 ) and π2 = (π’2 , π£2 ) be two edges in AuxπΌ (πΊ). If
π1 and π2 cross a certain edge π = (π₯, π¦), and π1 is ππππ ππ to π₯ than π2 , then the edge (π’1 , π£2 ) is also in
AuxπΌ (πΊ).
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 7
R AHUL JAIN AND R AGHUNATH T EWARI
y
u2 e2 v2
u1 v1
e1
f
x
Figure 3: Illustration of Lemma 3.6
π π π
Proof. Let π = (π£, πβ (π£)), π1 = (πβ (π£), πβπ (π£)) and π2 = (πβπ (π£), πβπ‘ (π£)). If πβ (π£) = πβπ (π£) then the
lemma trivially follows. Otherwise, we have two cases to consider:
π
Case 1 (π1 crosses π2 ): In this case, we will have (πβ (π£), πβπ‘ (π£)) in AuxπΌ (πΊ) by Lemma 3.5.
Case 2 (π1 does not cross π2 ): In this case, we have min(π, π) < min(π , π‘) < π < max(π , π‘) <
π π
max(π, π). Since π1 crosses π , we have the edge (πβ (π£), πβ (π£)) in AuxπΌ (πΊ) by Lemma 3.5.
π
This edge will cross π2 . Hence (πβ (π£), πβπ‘ (π£)) is in AuxπΌ (πΊ).
4 Pseudoseparators in a grid digraph
Imai et al. used a separator construction to solve the reachability problem in planar digraphs [9].
A separator is a set of vertices whose removal disconnects the graph into small components. The
class of grid digraphs is a subclass of planar digraphs. Grid graphs are known to have small
separators. However, for a grid digraph πΊ, the underlying undirected graph of AuxπΌ (πΊ) might
not have a small separator.
An essential property of a separator is that, for any two vertices, a path between the vertices
must contain a separator vertex if the vertices lie in two different components with respect to
the separator. This property can then be used to design a divide and conquer algorithm for
reachability where only separator vertices need to be marked and stored for traversal. Lemma 3.6
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 8
O N S OLVING R EACHABILITY IN G RID D IGRAPHS U SING A P SEUDOSEPARATOR
allows us to use edges as well since, at most, one vertex on each side of an edge needs to be
stored for traversal (the visited-vertex closest to the tail of the edge). Hence, we can use a slightly
weaker structure in place of a separator. We construct a structure called pseudoseparator (see
Definition 4.1). It is essentially a set of vertices and edges that can be used to divide the digraph
into components, such that a path from one component to another either takes a vertex of the
pseudoseparator or crosses an edge of the pseudoseparator.
For a digraph π» = (π1 , πΈ1 ) given along with its drawing, and a sub-digraph πΆ = (π2 , πΈ2 ) of π»,
define the digraph π» πΆ = (π3 , πΈ3 ) as π3 = π1 \ π2 and πΈ3 = πΈ1 \ {π β πΈ1 | β π β πΈ2 , π crosses π }.
We note that the digraph π» we will be working with throughout the article will be a sub-digraph
of an auxiliary digraph. Hence it will always come with a drawing.
Definition 4.1. Let πΊ be a grid digraph and π» be an induced sub-digraph of AuxπΌ (πΊ) with
β vertices. Let π : β β β be a function. A sub-digraph πΆ of π» is said to be an π (β)-
pseudoseparator of AuxπΌ (πΊ) if the size of every connected component in cc(π» πΆ) is at most
π (β). The size of πΆ is the number of vertices plus the number of edges of πΆ.
For an inducedsub-digraph π» of AuxπΌ (πΊ), an π (β)-pseudoseparator is a sub-digraph πΆ of π»
that has the property that, if we remove the vertices as well as all the edges that cross one of
the edges of the pseudoseparator, the digraph gets disconnected into small pieces. Moreover
for every edge π in π», if there exists distinct sets π1 and π2 in cc(π» πΆ) such that one of the
endpoints of π is in π1 and the other is in π2 , then there exists an edge π in πΆ such that π crosses
π . Hence any path in π» that connects two vertices in different components of π» πΆ must either
contain a vertex of πΆ or must contain an edge that crosses an edge of πΆ. We divide the digraph
using this pseudoseparator and give an algorithm that recursively solves each sub-digraph and
then combines their solution efficiently.
4.1 Constructing a pseudoseparator
Before working out the details below, we briefly comment on how to construct a pseudoseparator
of an inducedsub-digraph π» of AuxπΌ (πΊ). Ideally, we would have liked to have a set of cycles
of π» such that the surfaces obtained by cutting along these cycles have a bounded number of
vertices on it.However, such cycles might not exist. We instead pick a maximal subset of edges
from π» so that no two edges cross (see Definition 4.2 and Lemma 4.3). Then we triangulate the
resulting graph. We show that this triangulated graph has the required cycles and can be found
using Imai et al.βs separator algorithm. Call the triangulated graph π»
b and the separator vertices
as π. Since the cycles might have triangulated edges, we will add at most a constant number of
vertices and edges from π» to shield these triangulated edges. The vertex set of pseudoseparator
of π» will thus contain all the vertices of π and at most four additional vertices for each edge
of π»[π]
b that is not in π». The edge set of pseudoseparator of π» will contain all the edges of π»
which are also in π»[π]
b and at most four additional edges for each edge of π»[π]
b that is not in π».
Definition 4.2. Let πΊ be a grid digraph and π» be an induced sub-digraph of AuxπΌ (πΊ). We define
planar(π») as a sub-digraph of π». The vertex set of planar(π») is same as that of π». For an edge
π β π», let β be the block to which π belongs and let π€ be the lowest indexed vertex in that block.
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 9
R AHUL JAIN AND R AGHUNATH T EWARI
π π¦
Then π = (πβπ (π€), πβ (π€)) is in planar(π») if there exists no other edge π = (πβπ₯ (π€), πβ (π€)) in π» such
that min(π₯, π¦) < min(π, π) < max(π₯, π¦) < max(π, π).
In Lemma 4.3 we show that the digraph planar(π») is indeed planar. We also prove that the
subset of edges that we have picked from π» is a maximal subset such that no two edges cross.
Lemma 4.3. Let πΊ be a grid digraph and π» be an induced sub-digraph of AuxπΌ (πΊ). No two edges of
planar(π») cross each other. Moreover, for any edge π in π» that is not in planar(π»), there exists another
edge in planar(π») that crosses π.
π π
Proof. Let β be a block of AuxπΌ (πΊ) and π€ be the smallest index vertex of β . Let π = (πβ (π€), πβ (π€))
and π = (πβπ (π€), πβπ (π€)) be two edges of π» that cross. We have, by Lemma 3.3, that either
min(π, π) < min(π, π ) < max(π, π) < max(π, π ) or min(π, π ) < min(π, π) < max(π, π ) < max(π, π).
Hence, by our construction of planar(π»), atmost one of π and π belongs to it. Thus no two edges
of planar(π») cross.
For the second part, we will prove by contradiction. Let us assume that there exists
edges in π» which is not in planar(π») and also not crossed by an edge in planar(π»). We
π π
pick edge π = (πβ (π€), πβ (π€)) from them such that min(π, π) of that edge is minimum. Since
this edge is not in planar(π»), we have by definition, an edge π = (πβπ (π€), πβπ (π€)) such that
min(π, π ) < min(π, π) < max(π, π ) < max(π, π). We pick the edge π for which min(π, π ) is
π
minimum. Now, since this edge π is not in planar(π»), we have another edge π = (πβπ (π€), πβ (π€)) in
planar(π») such that min(π, π) < min(π, π ) < max(π, π) < max(π, π ). We pick π such that min(π, π)
is minimum and break ties by picking one whose max(π, π) is maximum. Now, we have the
following cases:
Case 1 (π < π < π < π ): Note that π» is an induced sub-digraph of AuxπΌ (πΊ). Thus, in this case, the
edge (πβπ (π€), πβπ (π€)) will be in π» due to Lemma 3.5. Since π < π < π < π, and π < min(π, π ),
this will contradict the way in which edge π was chosen.
π
Case 2 (π < π < π < π): In this case, the edge (πβπ (π€), πβ (π€)) will be in π» due to Lemma 3.5. This
π0
edge will cross π and hence not be in planar(π»). Thus, we have an edge π 0 = (πβπ (π€), πβ (π€))
0
in planar(π») such that min(π 0 , π 0) < π < max(π 0 , π 0) < π. We will thus have two subcases.
Case 2a (π < min(π 0 , π 0)): Here, we will have π < min(π 0 , π 0) < π < max(π 0 , π 0). Hence this
edge will cross π giving a contradiction to the first part of this Lemma.
Case 2b (min(π 0 , π 0) β€ π): Here, this edge should have been chosen instead of π contradict-
ing our choice of π.
The analysis of two remaining cases where π < π < π < π and π < π < π < π are similar to Cases 1
and 2 respectively.
Definition 4.4. Let πΊ be a grid digraph and π» be an induced sub-digraph of AuxπΌ (πΊ). The
graph π»
b is formed by first running Algorithm 1 on π» and then triangulating the underlying
undirected graph of the result
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 10
O N S OLVING R EACHABILITY IN G RID D IGRAPHS U SING A P SEUDOSEPARATOR
Input: An induced sub-digraph π» of AuxπΌ (πΊ)
1 Output all the vertices of π»;
2 Output all the edges of planar(π»);
3 foreach block β in π» do
4 foreach vertex π£ of π» in β do
π
5 π β the smallest positive integer such that πβ (π£) β π(π»);
π
6 if (π£, πβ (π£)) β πΈ(planar(π»)) then
π
7 Output the edge (π£, πβ (π£));
8 end
9 end
10 end
Algorithm 1: Completing the boundary of planar(π»)
Note that Algorithm 1 completes the boundary of each block. Thus, for any block, the
vertices in its boundary form a simple cycle. Since the interiors of these cycles are disjoint, there
is no edge that is drawn through more than one block in π». b Thus, each edge of π» b lies either
entirely inside one of the blocks, or lies completely outside the whole π Γ π grid.
Now, for each of those edges added to π» b as part of triangulation that is inside one of the
blocks, we define a set of at most four shield edges.
Definition 4.5. Let πΊ be a grid digraph and π» be an induced sub-digraph of AuxπΌ (πΊ). Let
π = (π£, π€) be an edge in π»
b such that π is inside one of the blocks and π is not in planar(π»). Let π
π π
and π be integers such that π€ = πβ (π£) and π£ = πβ (π€).
π
β’ Let π 1 be the largest integer such that π 1 < π and an edge π1 with endpoints π£ and πβ 1 (π£)
exists in planar(π»). π1 is undefined if no such integer exists.
π
β’ Let π 2 be the smallest integer such that π 2 > π and an edge π2 with endpoints π£ and πβ 2 (π£)
exists in planar(π»). π2 is undefined if no such integer exists.
π
β’ Let π1 be the largest integer such that π1 < π and an edge π3 with endpoints πβ 1 (π€) and π€
exists in planar(π»). π3 is undefined if no such integer exists.
π
β’ Let π 2 be the smallest integer such that π2 > π and an edge π4 with endpoints πβ 2 (π€) and
π€ exists in planar(π»). π4 is undefined if no such integer exists.
For π = 1, 2, 3, 4, the edges π π which are defined above are called shield edges of π.
We will be using the following Lemma, which was proven by Imai et al., to help us in the
construction of pseudoseparator.
Lemma 4.6. [9] For every π½ > 0, there exists a polynomial-time and π(β Λ 1/2+π½/2 )-space algorithm that
takes a β-vertex planar graph π as input and outputs a set of vertices π, such that |π| is π(β 1/2+π½/2 ) and
removal of π disconnects the graph into components of size π(β 1βπ½ ).
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 11
R AHUL JAIN AND R AGHUNATH T EWARI
Algorithm 2 describes how to construct a sub-digraph of π» which we call psep(π»). In
Lemma 4.8 we show that psep(π») is a pseudoseparator of π».
Input: Aninduced sub-digraph π» of AuxπΌ (πΊ) and a positive number π½
Output: The digraph psep(H)
1 Construct π» b from π»;
2 Find a set π of vertices in π»b which divides it into components of size π(π 1βπ½ ) by
applying Lemma 4.6 ;
3 Output all the vertices of π;
4 Output those edges of π» which are also (in its undirected form) in π»[π];
b
5 foreach edge π = (π£, π€) of π» b do
6 if π is inside a block of π»
b and π β πΈ(planar(π»)) and both endpoints of π are in π then
7 Output all the shield edges of π along with their end vertices.
8 end
9 end
Algorithm 2: Construction of psep(H)
Lemma 4.7. Let πΊ be a grid digraph , and π» be aninduced sub-digraph of AuxπΌ (πΊ). For every π½ > 0,
Λ 1/2+π½/2 )-space algorithm that takes π» as input and outputs
there exists a polynomial-time and π(β
psep(H).
Proof. To prove this lemma, we analyse the space and time complexity of Algorithm 2. We will
b is constructed from π» in logspace. To see it, we first note that we can decide if an
first see that π»
edge π of π» belong to planar(π») in logspace by checking if π satisfies the condition required by
Definition 4.2. Next, the boundary of planar(π») is completed in logspace by using Algorithm 1.
Finally we triangulate the resultant graph in logspace: For every face π in the resultant graph, we
connect each vertex of π to the lowest-indexed vertex of π . The space complexity of construction
of psep(H) is thus dominated by the space required by step 2 of Algorithm 2. By Lemma 4.6, we
know that this step requires π(β 1/2+π½/2 ) space. Hence, the space required by Algorithm 2 is
π(β 1/2+π½/2 ). Each step of Algorithm 2 is performed in polynomial time, hence the total time
complexity is bounded by a polynomial.
Lemma 4.8. Let πΊ be a grid digraph , and π» be aninduced sub-digraph of AuxπΌ (πΊ). The digraph
psep(π») is a β 1βπ½ -pseudoseparator of π».
To prove Lemma 4.8, we first show a property of triangulated graphs that we use in our
construction of pseudoseparator. We know that a simple cycle in a planar embedding of a
planar graph divides the plane into two parts. We call these two parts the two sides of the cycle.
Lemma 4.9. Let πΊ be a triangulated planar graph, and π be a subset of its vertices. For each pair of
vertices π’, π£ belonging to different components of πΊ \ π, a cycle in πΊ[π] exists, such that π’ and π£ belong
to different sides of this cycle.
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 12
O N S OLVING R EACHABILITY IN G RID D IGRAPHS U SING A P SEUDOSEPARATOR
Proof. To prove the Lemma, we first need some terminology. We call a set of faces a region of
edge-connected faces if they induce a connected subgraph in the dual graph. We can orient the
edges of an undirected planar simple cycle to make it a directed cycle. This can help us identify
the two sides of the cycle as interior (left-side) and exterior (right-side).
Let πΆ be a component of πΊ \ π and π0 be the set of vertices of π adjacent to at least one of the
vertices of πΆ in πΊ. Let πΉ be the set of triangle faces of πΊ to which at least one vertex of πΆ belongs.
Let πΊΛ be the dual graph of πΊ and πΊ[πΉ] Λ be the subgraph induced by πΉ on this dual graph.
We first observe that since we have started with a triangulated graph, the vertices of any face
π of πΉ will either belong to πΆ or π0.
Let π1 and π2 be two arbitrary faces of πΉ. We will first show that πΉ is a region of edge-connected
faces by showing that there exists a path between π1 and π2 in πΊ[πΉ]. Λ Let π£ 1 be a vertex of πΆ
which belongs to π1 . Similarly, let π£2 be a vertex of πΆ which belongs to π2 . Let the length of
shortest path between π£ 1 and π£ 2 in πΊ \ π be π. We prove our claim by induction on π. If π = 0,
then π£ 1 = π£ 2 . We know that the set of faces that share a vertex induce a connected subgraph
in the dual graph, hence our claim holds for π = 0. Now, we assume that our claim holds for
path length π = β β 1. To prove that our claim holds for π = β , let (π£3 , π£2 ) be the last edge in the
shortest path from π£ 1 to π£ 2 . Let π3 be a face with both π£ 3 and π£ 2 in its boundary. Since the length
of shortest path from π£ 1 to π£ 3 is β β 1, by induction hypothesis, there exists a path between π1
Λ
and π3 in πΊ[πΉ]. Since π3 and π2 share the vertex π£2 , there is a path between π3 and π2 in πΊ[πΉ]. Λ
Combining these two paths, we get a path between π1 and π2 in πΊ[πΉ] Λ which proves our claim.
Miller proved that the boundary of a region of edge-connected faces is a set of edge-disjoint
simple cycles which can be oriented such that they have disjoint exteriors [12]. We claim that all
the vertices of any boundary cycle of πΉ are contained in π0. We prove this claim by contradiction.
Let us assume that π£ is a vertex in a boundary cycle of πΉ that is not in π0. In this case, π£ belongs
to πΆ. Consider an edge (π£, π€) of the boundary cycle. Let ππ and ππ be the two faces that shares
the edge (π£, π€). Let π£ π and π£ π be the third vertex of ππ and ππ respectively. Since π£ π , π£ π and π€
are all connected to π£, they are in either π0 or πΆ. Thus both ππ and ππ are in πΉ. However, this
contradicts that (π£, π€) is at boundary of πΉ.
Thus, we have proved that the vertices of a connected component of πΊ \ π are contained
inside a set of edge-disjoint simple cycles with disjoint exteriors. The vertices of all such cycles
are contained in π. Hence the lemma follows.
Proof of Lemma 4.8. Let πΆ = psep(π»). Let π be the set of vertices obtained from π» b by using
Lemma 4.6. We claim that if any two vertices π’ and π£ belong to different connected components
of π»
b \ π, then it belongs to different components of cc(π» πΆ). We prove this by contradiction.
Let us assume that it is not true. Then there is an edge π in π» and two distinct sets π1 and π2 of
cc(π»b \ π) such that one of the end point of π is in π1 , the other is in π2 and π does not cross any
π
of the edges of psep(π»). Without loss of generality, let π = (π£, πβ (π£)), for some block β , where
π
π£ β π1 and πβ (π£) is not in π1 (we pick the edge π such that π is minimum for any choice of π£).
π
Due to Lemma 4.9, it follows that there exists an edge π in π»[π]
b such that π = ((πβ (π£)), πβπ (π£))
and that π crosses π . This edge π is a triangulation edge, for otherwise it is also in psep(H)
giving us a contradiction. We orient the triangulation edge so that π < π < π. Now, since π is
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 13
R AHUL JAIN AND R AGHUNATH T EWARI
not in planar(π»), by Lemma 4.3 there exists at least one edge that crosses it and is in planar(π»).
Let π = (πβπ (π£), πβπ‘ (π£)) be one such edge such that π‘ β π is maximum1 We thus have the following
cases:
Case 1 (π < π < π < π < π‘): In this case, since π crosses π, by Lemma 3.5, we have that the edge
π
π 0 = (πβπ (π£), πβ (π£)) is also in π». π 0 also crosses π . Since π β π < π, existence of π 0 contradicts
our choice of π.
Case 2 (π < π‘ < π < π < π): In this case, since π crosses π, by Lemma 3.5, we have that the edge
π 0 = (π£, πβπ‘ (π£)) is also in π». π 0 also crosses π . Since π‘ < π, existence of π 0 contradicts our
choice of π.
π
Case 3 (π‘ < π < π < π < π ): In this case, the edge π 0 = (πβπ (π£), πβ (π£)) will also be in π». π 0 will cross
π and hence will not be in planar(π»). By Lemma 4.3, there exists an edge π 0 = (πβπ (π£), πβπ‘ (π£))
0 0
in planar(π») that crosses π 0. Since both π 0 and π are in planar(π»), these edges do not cross
each other.
Using the fact that π 0 crosses π 0 and π 0 does not cross π, we get the following:
π‘ β€ min(π 0 , π‘ 0) < π < max(π 0 , π‘ 0) < π
Consequently, π‘ 0 β π 0 > π‘ β π and π 0 crosses π. This contradicts our choice of π.
Case 4 (π < π < π < π‘ < π): In this case, since π crosses π, by Lemma 3.5, we have that the edge
π 0 = (π£, πβπ‘ (π£)) is in π». π 0 also crosses π and hence π 0 was not in planar(π»). Thus there will
exist an edge in planar(π») which crosses π 0 by Lemma 4.3. Let π 0 = (πβπ (π£), πβπ‘ (π£)) be the
0 0
edge in planar(π») that crosses π 0 such that π‘ 0 β π 0 is maximum. We have the following
subcases:
Case 4a (π 0 < π < π‘ < π < π‘ 0): In this case, since π 0 crosses π, by Lemma 3.5, we have that
π
the edge π 00 = (πβπ (π£), πβ (π£)) is also in π». π 00 also crosses π . Since π β π 0 < π, existence
0
of π 00 contradicts our choice of π.
Case 4b (π < π‘ 0 < π‘ < π 0 < π): In this case, we see that since π and π 0 are both in planar(π»),
they do not cross each other. Therefore. π‘ 0 β€ π and consequently π‘ 0 < π. Thus, π 0
crosses π and by Lemma 3.5, the edge π 00 = (π£, πβπ‘ (π£)) is also in π». π 00 also crosses π .
0
Since π‘ 0 < π, existence of π 00 contradicts our choice of π.
Case 4c (π‘ 0 < π < π‘ < π < π 0): In this case, the edge π 00 = (πβπ (π£), πβπ‘ (π£)) will also be in π».
0
π 00 will cross π and hence will not be in planar(π»). By Lemma 4.3, there exists an
edge π 00 = (πβπ (π£), πβπ‘ (π£)) in planar(π») that crosses π 00. Since π 00, π 0 and π are all in
00 00
planar(π»), these edges do not cross each other.
Using the fact that π 00 crosses π 00, π 00 does not cross π 0 and π 00 does not cross π; we get
the following:
1We note that we do not consider the absolute value of the π‘ β π , rather we consider the actual value. π‘ β π can
hence be negative for an edge.
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 14
O N S OLVING R EACHABILITY IN G RID D IGRAPHS U SING A P SEUDOSEPARATOR
π€
π’ π£
π
π’ π’0 π£0
π£
(a) The π -π‘ path takes a vertex of the separator (b) The π -π‘ path crosses an edge of the separator
Figure 4
π‘ 0 β€ min(π 00 , π‘ 00) < π < π‘ < max(π 00 , π‘ 00) < π 0
Consequently, π‘ 00 β π 00 > π‘ 0 β π 0 and π 00 crosses π 0. This contradicts our choice of π 0.
Case 4d (π < π 0 < π‘ < π‘ 0 < π): In this case, we see that since π and π 0 are both in planar(π»),
they do not cross each other. Therefore π 0 β€ π and consequently π 0 < π. Thus, π 0
crosses π and π‘ 0 β π 0 > π‘ β π . This contradicts our choice of π.
In other cases, if π is picked such that one of its vertices is common with π , then π will cross a
π βππππ edge of π , giving a contradiction. If π is picked such that π cross π , then it contradicts the
fact that both of them are in π»,b which is a planar digraph .
Summarizing Lemmas 4.7 and 4.8 we have Theorem 4.10.
Theorem 4.10. Let πΊ be a grid digraph and π» be aninduced subgraph of AuxπΌ (πΊ) with β vertices. For
Λ 1/2+π½/2 )-space and polynomial-time algorithm that takes π» as
any constant π½ > 0, there exists an π(β
input and outputs an β -pseudoseparator of size π(β 1/2+π½/2 ).
1βπ½
5 Algorithm to solve reachability in the auxiliary digraph
In this section, we discuss the grid digraph reachability algorithm. Let πΊ be a grid digraph
having eπ vertices. By induction, we assume that we have access to an induced subgraph π» of
AuxπΌ (πΊ), containing β vertices. Below we describe a recursive procedure AuxReach(π», π₯, π¦) that
outputs true if there is a path from π₯ to π¦ in π» and outputs false otherwise.
5.1 Description of the algorithm AuxReach
First we construct a β 1βπ½ -pseudoseparator πΆ of π», using Theorem 4.10. We also ensure that π₯
and π¦ are part of πΆ (if not then we add them). Let πΌ1 , πΌ2 , . . . , πΌβ be the connected components of
π» πΆ.
We maintain an array called visited of size |πΆ| to mark vertices or edges of the pseudoseparator
πΆ. Each cell of visited corresponds to a distinct vertex or edge of πΆ. For a vertex π£ in πΆ, we set
visited[π£] := 1 if there is a path from π₯ to π£ in π», else it is set to 0. For an edge π = (π’, π£) in πΆ, we
set visited[π] := π’ 0 if (i) there is an edge π = (π’ 0 , π£ 0) that crosses π, (ii) there is a path from π₯ to π’ 0
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 15
R AHUL JAIN AND R AGHUNATH T EWARI
in π» and (iii) π is the closest such edge to π’. Else visited[π] is set to NULL. Initially, for all vertex
π£ β πΆ, visited[π£] := 0 and for all edges π β πΆ, visited[π] := NULL. We say that a vertex π£ is marked
if either visited[π£] = 1 or visited[π] = π£ for some edge π.
First set visited[π₯] := 1. We then perform an outer loop with β iterations and in each iteration
update certain entries of the array visited as follows. For every vertex π£ β πΆ, the algorithm sets
visited[π£] := 1 if there is a path from a marked vertex to π£ such that the internal vertices of that
path all belong to only one component πΌ π . Similarly, for each edge π = (π’, π£) of πΆ, the algorithm
sets visited[π] := π’ 0 if (i) there exists an edge π = (π’ 0 , π£ 0) which crosses π, (ii) there is a path
from a marked vertex to π’ 0 such that the internal vertices of that path all belong to only one
component πΌ π and, (iii) π is the closest such edge to π’. Finally we output true if visited[π¦] = 1 else
output false. We use the procedure AuxReach recursively to check if there is a path between two
vertices in a single connected component of π» πΆ. A formal description of AuxReach is given in
Algorithm 3.
5.2 Proof of correctness of AuxReach
Let π be a path from π₯ to π¦ in π». Suppose π passes through the components πΌ π1 , πΌ π2 , . . . , πΌ ππΏ in
this order. The length of this sequence is at most |π» |. As the path leaves the component πΌ π π and
goes into πΌ π π+1 , it can do in the following two ways only:
1. The path exits πΌ π π through a vertex π€ of pseudoseparator as shown in Figure 4a. In this
case, Algorithm 3 marks the vertex π€.
2. The path exits πΌ π π through an edge (π’, π£) whose other endpoint is in πΌ π π+1 . By Lemma 3.6,
this edge will cross an edge π = (π₯ 0 , π¦ 0) of the pseudoseparator. In this case, Algorithm 3
marks the vertex π’ 0, such that there is an edge (π’ 0 , π£ 0) that crosses π as well and (π’ 0 , π£ 0) is
closer than (π’, π£) to π₯ 0 and there is a path in πΌ π π from a marked vertex to π’ 0. By Lemma 3.6,
the edge (π’ 0 , π£) is in π» as well.
Thus after the π-th iteration, AuxReach traverses the fragment of the path in the component
πΌ π π and either marks its endpoint or a vertex which is closer to the edge π of πΆ which the path
crosses. Finally, π¦ is marked after πΏ iterations if and only if there is a path from π₯ to π¦ in π».
We give a formal proof of correctness in Lemma 5.1. For a path π = (π’1 , π’2 , . . . π’π‘ ), we define
tail(π) := π’1 and head(π) := π’π‘ .
Lemma 5.1. Let πΊ be a grid digraph and π» be aninduced subgraph of AuxπΌ (πΊ). Then for any two
vertices π₯, π¦ in π», there is a path from π₯ to π¦ in π» if and only if AuxReach(π», π₯, π¦) returns true.
Proof. Firstly observe that, if a vertex is marked, then there is a path from some other marked
vertex to that vertex in π». Hence if there is no path from π₯ to π¦ then π¦ is never marked by
AuxReach and hence AuxReach returns false.
Now let π be a path from π₯ to π¦ in π». We divide the path into subpaths π1 , π2 , . . . , πβ , such
that for each π, all vertices of ππ belong to π βͺ π(πΆ) for some connected component π in cc(π» πΆ)
and either (i) head(ππ ) = tail(ππ+1 ), or (ii) π π = (head(ππ ), tail(ππ+1 )) is an edge that crosses some
edge ππ β πΆ. By Definition 4.1, we have that if condition (i) is true then head(ππ ) is a vertex in πΆ,
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 16
O N S OLVING R EACHABILITY IN G RID D IGRAPHS U SING A P SEUDOSEPARATOR
Input: An induced subgraph π» of AuxπΌ (πΊ) and two vertices π₯ and π¦ in π» (let πΊ be an
π Γ π grid digraph and β = |π(π»)|)
Output: true if there is a path from π₯ to π¦ in π» and false otherwise
1 if β β€ π 1/8 then Use DFS to solve the problem; /* π is a global variable where
πΊ is an π Γ π grid digraph */
2 else
3 Compute a β 1βπ½ -pseudoseparator πΆ of π» using Theorem 4.10;
4 πΆ β πΆ βͺ {π₯, π¦};
5 foreach edge π in πΆ do visited[π] β NULL;
6 foreach vertex π£ in πΆ do visited[π£] β 0;
7 visited[π₯] β 1;
8 for π = 1 to |π» | do
9 foreach edge π = (π’, π£) β πΆ do
10 closestedge β NULL;
11 foreach marked vertex π€ do
12 foreach π β cc(π» πΆ) do
13 foreach edge π = (π’ 0 , π£ 0) such that π crosses π do
14 if AuxReach(π»[π βͺ {π€, π’ 0 }], π€, π’ 0) = true then
15 if closestedge = NULL or π is closer to π than closestedge then
16 visited[π] β π’ 0;
17 closestedge β π ;
18 end
19 end
20 end
21 end
22 end
23 end
24 foreach vertex π£ β πΆ do
25 if βπ€βπ such that π€ is a marked vertex and π β cc(π» πΆ) and
AuxReach(π»[π βͺ {π€, π£}], π€, π£) = true)) then
26 visited[π£] β 1;
27 end
28 end
29 end
30 if visited[π¦] = 1 then return true;
31 else return false;
32 end
Algorithm 3: AuxReach(π», π , π‘)
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 17
R AHUL JAIN AND R AGHUNATH T EWARI
and if condition (ii) is true then head(ππ ) and tail(ππ+1 ) belong to two different components of
cc(π» πΆ) and π π is the edge between them.
We claim that after π-th iteration of loop in Line 8 of Algorithm 3, either of the following two
statements hold:
1. head(ππ ) is a vertex in πΆ and visited[head(ππ )] = 1.
2. There exists an edge ππ = (π’π , π£ π ) of πΆ such that the edge π π = (head(ππ ), tail(ππ+1 )) crosses
ππ and there is an edge π π = (π’π0 , π£ 0π ) which crosses ππ as well, such that π π is closer to π’π than
π π and visited[ ππ ] = π’π0.
We prove the claim by induction. The base case holds since π₯ is marked at the beginning. We
assume that the claim is true after the (π β 1)-th iteration. We have that ππ belongs to π βͺ π(πΆ)
for some connected component π in cc(π» πΆ).
Case 1 (head(ππβ1 ) = tail(ππ ) = π€(say)): By induction hypothesis π€ was marked after the (π β 1)-
th iteration. If head(ππ ) is a vertex in πΆ then it will be marked after the π-th iteration in
Line 26. On the other hand if π π = (head(ππ ), tail(ππ+1 )) is an edge that crosses some edge
ππ = (π’π , π£ π ) β πΆ then in the π-th iteration in Line 16, the algorithm marks a vertex π’π0 such
that, π π = (π’π0 , π£ 0π ) is the closest edge to π’π that crosses ππ and there is a path from π€ to π’π0.
Case 2 (π πβ1 = (head(ππβ1 ), tail(ππ )) crosses some edge ππβ1 = (π’πβ1 , π£ πβ1 ) β πΆ): By induction hy-
pothesis, there is an edge π πβ1 = (π’πβ1 0
, π£ 0πβ1 ) which crosses ππβ1 as well, such that π πβ1 is
closer to π’πβ1 than π πβ1 and visited[ ππβ1 ] = π’πβ1 0
. By Lemma 3.6 there is an edge in π» between
π’πβ1 and tail(ππ ) as well. Now if head(ππ ) is a vertex in πΆ then it will be marked after the
0
π-th iteration in Line 26 by querying the digraph π»[π βͺ {π’πβ1 0
, head(ππ )}]. On the other
hand if π π = (head(ππ ), tail(ππ+1 )) is an edge that crosses some edge ππ = (π’π , π£ π ) β πΆ then in
the π-th iteration in Line 16, AuxReach queries the digraph π»[π βͺ {π’πβ1 0
, π’π0 }] and marks a
vertex π’π such that, π π = (π’π , π£ π ) is the closest edge to π’π that crosses ππ and there is a path
0 0 0
from π’πβ10
to π’π0.
Our subroutine solves reachability in a subgraph π» (having size β) of AuxπΌ (πΊ). We do
not explicitly store a component of cc(π» πΆ), since it might be too large. Instead, we identify
a component with the lowest indexed vertex in it and use Reingoldβs algorithm on π» πΆ
to determine if a vertex is in that component. We require π(β e 1/2+π½/2 ) space to compute
a β 1βπ½ -pseudoseparator by Theorem 4.10. We can potentially mark all the vertices of the
pseudoseparator and for each edge of the pseudoseparator we mark at most one additional
vertex. Since the size of the pseudoseparator is at most π(β 1/2+π½/2 ), we require π(βe 1/2+π½/2 )
space. The algorithm recurses on a digraph with β 1βπ½ vertices. Since we stop the recursion
when β β€ π 1/8 (Line 1 of Algorithm 3), the depth of the recursion is at most dβ3/log(1 β π½)e,
which is a constant.
Since the digraph π» is given implicitly in our algorithm, an additional polynomial overhead
is involved in obtaining its vertices and edges. However, the total time complexity remains a
polynomial in the number of vertices since the recursion depth is constant.
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 18
O N S OLVING R EACHABILITY IN G RID D IGRAPHS U SING A P SEUDOSEPARATOR
Lemma 5.2. Let πΊ be an π Γ π grid digraph and π» beaninduced subgraph of AuxπΌ (πΊ) with β vertices.
For every π½ > 0, AuxReach runs in π(β
e 1/2+π½/2 ) space and polynomial time.
Proof. Since the size of a component π in cc(π» πΆ) might be too large, we will not explicitly
store it. Instead we identify a component by the lowest index vertex in it and use Reingoldβs
algorithm on π» πΆ to determine if a vertex is in π. Let π(π, β) and π(π, β) denote the space
and time complexity functions respectively of AuxReach, where πΊ is an π Γ π grid digraph and
β is the number of vertices in the digraph π». As noted earlier the depth of the recursion is at
most π := dβ3/log(1 β π½)e.
Consider π(π, β) for any β > π 1/8 . By Theorem 4.10, we require π(βe 1/2+π½/2 ) space to execute
Line 3. We can potentially mark all the vertices of πΆ and for each edge π of πΆ we store at
most one additional vertex in visited[π]. Since the size of πΆ is at most π(β 1/2+π½/2 ), we require
e 1/2+π½/2 ) space to store πΆ. By induction, a call to AuxReach in line 16 and 26 requires π(π, β 1βπ½ )
π(β
space which can be subsequently reused. Hence the space complexity satisfies the following
recurrence. Then, (
π(π, β 1βπ½ ) + π(β
e 1/2+π½/2 ) β > π 1/8
π(π, β) =
π(β)
e otherwise.
Solving we get π(π, β) = π(β
e 1/2+π½/2 + π 1/4 ).
Next we measure the time complexity of AuxReach. Consider the case when β > π 1/8 . The
total number of steps in AuxReach is some polynomial in β, say π. Moreover AuxReach makes π
calls to AuxReach, where π is some other polynomial in β. Hence π(β) β€ π(β). Then,
(
π Β· π(β 1βπ½ ) + π β > π 1/8
π(π, β) =
π(β) otherwise.
Solving the above recurrence we get π(π, β) = π(π Β· π π + π 1/4 ) = π(π 2π + π 1/4 ).
6 Solving grid digraph
Let πΊ be an π Γ π grid digraph . As mentioned in the introduction, our objective is to run the
algorithm 3 on the digraph AuxπΌ (πΊ). Consider two vertices π₯ and π¦ of AuxπΌ (πΊ). Note that, by
definition, π¦ is reachable from π₯ in AuxπΌ (πΊ) if and only if π¦ is reachable from π₯ in πΊ. Hence it is
sufficient to work with the digraph AuxπΌ (πΊ). However, we do not have explicit access to the
edges of AuxπΌ (πΊ). Note that we can obtain the edges of AuxπΌ (πΊ) by solving the corresponding
subgrid of πΊ to which that edge belongs. If the subgrid is small enough, then we use a standard
linear space-traversal algorithm. Otherwise, we use our algorithm recursively on the subgrid.
Algorithm 4 outlines this method.
Consider an π bΓπ b grid digraph πΊ.
b Let π(π b ) be the space complexity and π(π b ) be the time
complexity of executing GridReach on πΊ. Note that the size of AuxπΌ (πΊ) is at most π
b b b 1+πΌ . For
π
b > π , the space required to solve the grid digraph
1/8
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 19
R AHUL JAIN AND R AGHUNATH T EWARI
Input: A grid digraph πΊ b and two vertices b π , b
π‘ of πΊ
b and a positive integer π
Output: true if there is a path from π to π‘ in πΊ and false otherwise
if πΊ
b is smaller than π 1/8 Γ π 1/8 grid then
Use Depth-First Search to solve the problem;
end
else
Use ImplicitAuxReach(AuxπΌ (πΊ), b π , b
π‘) to solve the problem;
/* ImplicitAuxReach executes the same way as AuxReach except for the
case when it queries an edge (π’, π£) in a block π΅ of AuxπΌ (πΊ). In this
case, the query is answered by calling GridReach(π΅, π’, π£, π) where π΅ is
the subgrid in which edge (π’, π£) might belong. */
end
Algorithm 4: GridReach(πΊ, bbπ , b
π‘, π)
is π(π
b ) = π(π
b 1βπΌ ) + π((
e π b 1+πΌ )1/2+π½/2 ). This is because, a query whether (π’, π£) β πΊinvokes
b a
recursion which requires π(π b ) space and the main computation of ImplicitAuxReach can be
1βπΌ
done using π((
e π b 1+πΌ )1/2+π½/2 ) space. Hence we get the following recurrence for space complexity.
(
π(π
b 1βπΌ ) + π((
e π b 1+πΌ )1/2+π½/2 ) π
b > π 1/8
π(π
b) =
π(
eπ b 1/4 ) otherwise
Similar to the analysis of AuxReach, for appropriate polynomials π and π, the time complexity
satisfies the following recurrence:
(
π(π
b ) Β· π(π
b 1βπΌ ) + π(π
b) π
b > π 1/8
π(π
b) =
π(π
b) otherwise.
Solving we get π(π) = π(π
e 1/2+π½/2+πΌ/2+πΌπ½/2 ) and π(π) = poly(π). For any constant π > 0, we can
chose πΌ and π½ such that π(π) = π(π 1/2+π ).
7 Conclusion
Our result improves upon the known timeβspace bounds on the grid digraph . Asano et al. [4]
used a clever idea of exploiting the grid structure of the input digraph to reduce its size. Their
exploitation destroyed the grid structure of the input digraph , but they did not go far enough
to destroy its planar structure as well. Our exploitation goes a step further. We get a non-planar
auxiliary digraph that is smaller as a result and has just enough structure to solve reachability
in a space-efficient manner. It remains to be seen if the structure could be further exploited to
get a smaller auxiliary-like digraph in which reachability can be solved.
It is known that reachability in planar digraph s can be reduced to reachability in grid
digraph s in logarithmic space [1]. However, such a reduction results in at least a quadratic
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 20
O N S OLVING R EACHABILITY IN G RID D IGRAPHS U SING A P SEUDOSEPARATOR
blow-up in the size of the digraph . In principle, it would seem that an improvement to the state
of the art for the planar digraph can be obtained by improving the result for grid digraph s.
However, we feel that this would be a difficult direction to go. Note that we solve an β-vertex
auxiliary digraph in π(β 1/2+π½/2 ) space as a subroutine for our griddigraph algorithm. A planar
digraph with its embedding can be thought of as an auxiliary digraph , and hence our algorithm
contains within itself a solution to the planar digraph as well. For this reason, we feel that
directly solving a planar digraph would be easier than going down the grid digraph routine.
A significantly different approach would be required to directly design an algorithm for grid
digraph , one which does not use a solution for the class of planar digraph s, or its superclass, as
a subroutine.
References
[1] Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, and Sambud-
dha Roy: Planar and grid graph reachability problems. Theory Computing Sys., 45(4):675β723,
2009. [doi:10.1007/s00224-009-9172-z] 2, 20
[2] Eric Allender and Meena Mahajan: The complexity of planarity testing. Inform. Comput.,
189(1):117β134, 2004. Preliminary version in STACSβ00. [doi:10.1016/j.ic.2003.09.002] 4
[3] Tetsuo Asano and Benjamin Doerr: Memory-constrained algorithms for shortest path
problem. In Proc. 23rd Canad. Conf. Comput. Geom. (CCCGβ11), pp. 1β4, 2011. cccg.ca. 3
β
[4] Tetsuo Asano, David Kirkpatrick, Kotaro Nakagawa, and Osamu Watanabe: π( Λ π)-space
and polynomial-time algorithm for planar directed graph reachability. In Proc. Internat.
Symp. Math. Foundations of Comp. Sci. (MFCSβ14), pp. 45β56. Springer, 2014. [doi:10.1007/978-
3-662-44465-8_5, ECCC:TR14-071] 2, 3, 20
[5] Ryo Ashida and Kotaro Nakagawa: π(π Λ 1/3 )-space algorithm for the grid graph reachability
problem. In Proc. 34th Internat. Symp. Comput. Geom. (SoCGβ18), pp. 5:1β13. Schloss Dagstuhlβ
Leibniz-Zentrum fuer Informatik, 2018. [doi:10.4230/LIPIcs.SoCG.2018.5, arXiv:1803.07097]
3
[6] Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, and Baruch Schieber: A sublinear space,
polynomial time algorithm for directed s-t connectivity. SIAM J. Comput., 27(5):1273β1282,
1998. Preliminary version in SCTβ92. [doi:10.1137/S0097539793283151] 2
[7] Diptarka Chakraborty, Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran, and
Lin F. Yang: New time-space upperbounds for directed reachability in high-genus
and π»-minor-free graphs. In Proc. 34th Found. Softw. Techn. Theoret. Comp. Sci. Conf.
(FSTTCSβ14), pp. 585β595. Schloss DagstuhlβLeibniz-Zentrum fuer Informatik, 2014.
[doi:10.4230/LIPIcs.FSTTCS.2014.585, ECCC:TR14-035] 2
[8] Diptarka Chakraborty and Raghunath Tewari: An π(π π ) space and polynomial time
algorithm for reachability in directed layered planar graphs. ACM Trans. Comput. Theory,
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 21
R AHUL JAIN AND R AGHUNATH T EWARI
9(4):19:1β11, 2017. Preliminary version in ISAACβ15. [doi:10.1145/3154857, arXiv:1501.05828,
ECCC:TR15-016] 2
[9] Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, and Osamu Watanabe:
An π(π 2 +π )-space and polynomial-time algorithm for directed planar reachability. In
1
Proc. 28th IEEE Conf. on Comput. Complexity (CCCβ13), pp. 277β286. IEEE Comp. Soc., 2013.
[doi:10.1109/CCC.2013.35] 2, 3, 8, 11
[10] Rahul Jain and Raghunath Tewari: An π(π 1/4+π ) space and polynomial algorithm
for grid graph reachability. In Proc. 39th Found. Softw. Techn. Theoret. Comp. Sci. Conf.
(FSTTCSβ19), pp. 19:1β14. Schloss DagstuhlβLeibniz-Zentrum fuer Informatik, 2019.
[doi:10.4230/LIPIcs.FSTTCS.2019.19] 1
[11] Sampath Kannan, Sanjeev Khanna, and Sudeepa Roy: STCON in directed
unique-path graphs. In Proc. 28th Found. Softw. Techn. Theoret. Comp. Sci. Conf.
(FSTTCSβ08), pp. 256β267. Schloss DagstuhlβLeibniz-Zentrum fuer Informatik, 2008.
[doi:10.4230/LIPIcs.FSTTCS.2008.1758] 2
[12] Gary L. Miller: Finding small simple cycle separators for 2-connected planar graphs. J.
Comput. System Sci., 32(3):265β279, 1986. Preliminary version in STOCβ84. [doi:10.1016/0022-
0000(86)90030-9] 13
[13] Omer Reingold: Undirected connectivity in log-space. J. ACM, 55(4):17:1β24, 2008. Prelimi-
nary version in STOCβ05. [doi:10.1145/1391289.1391291] 2, 4
[14] Walter J. Savitch: Relationships between nondeterministic and deterministic tape com-
plexities. J. Comput. System Sci., 4(2):177β192, 1970. [doi:10.1016/S0022-0000(70)80006-X]
2
[15] Derrick Stolee and N. V. Vinodchandran: Space-efficient algorithms for reachability in
surface-embedded graphs. In Proc. 27th IEEE Conf. on Comput. Complexity (CCCβ12), pp.
326β333. IEEE Comp. Soc., 2012. [doi:10.1109/CCC.2012.15, ECCC:TR10-154] 2
[16] Avi Wigderson: The complexity of graph connectivity. In Proc. Internat. Symp. Math.
Foundations of Comp. Sci. (MFCSβ92), pp. 112β132. Springer, 1992. [doi:10.1007/3-540-55808-
X_10] 2
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 22
O N S OLVING R EACHABILITY IN G RID D IGRAPHS U SING A P SEUDOSEPARATOR
AUTHORS
Rahul Jain
Research associate
Department of Theoretical Computer Science
FernuniversitΓ€t in Hagen
Germany
rahul jain fernuni-hagen de
https://www.fernuni-hagen.de/ti/en/team/rahul.jain
Raghunath Tewari
Associate professor
Department of Computer Science and Engineering
Indian Institute of Technology Kanpur
rtewari cse iit ac in
https://www.cse.iitk.ac.in/users/rtewari
ABOUT THE AUTHORS
Rahul Jain is a postdoctoral research associate at FernuniversitΓ€t in Hagen, Germany.
He obtained his doctorate at the Indian Institute of Technology Kanpur, India in
2020 under Dr. Raghunath Tewari.
Raghunath Tewari is an Associate Professor in the Computer Science and Engi-
neering Department at the Indian Institute of Technology Kanpur. He obtained
his undergraduate degree in mathematics and computer science from Chennai
Mathematical Institute in 2005. Thereafter he did his Masters in 2007 and Ph. D. in
2011 in computational complexity theory at the University of Nebraska β Lincoln
under Dr. N. V. Vinodchandran. He is interested in computational complexity
theory, algorithms and graph theory.
T HEORY OF C OMPUTING, Volume 19 (2), 2023, pp. 1β23 23