Theory of Computing
-------------------
Title     : On Solving Reachability in Grid Digraphs using a Pseudoseparator
Authors   : Rahul Jain and Raghunath Tewari
Volume    : 19
Number    : 2
Pages     : 1-23
URL       : https://theoryofcomputing.org/articles/v019a002

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 $O(n^{1/2 + \epsilon})$ space. In 2018, the space
complexity was improved to $\tilde{O}(n^{1/3})$ by Ashida and Nakagawa
(SoCG'18).

In this paper, we show that there exists a polynomial-time algorithm
that uses $O(n^{1/4 + \epsilon})$ space to solve the reachability
problem in a grid digraph containing $n$ 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'19).