pdf icon
Volume 19 (2023) Article 2 pp. 1-23
On Solving Reachability in Grid Digraphs using a Pseudoseparator
Received: January 13, 2020
Revised: May 25, 2022
Published: August 26, 2023
Download article from ToC site:
[PDF (507K)] [PS (2138K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: graph reachability, grid graph, graph algorithm, sublinear space algorithm
Categories: algorithms, graphs, graph algorithms, graph reachability, grid graph, sublinear space
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).