Revised: May 25, 2022

Published: August 26, 2023

**Keywords:**graph reachability, grid graph, graph algorithm, sublinear space algorithm

**ACM Classification:**G.2.2

**AMS Classification:**68Q25

**Abstract:**
[Plain Text Version]

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).