Volume 19 (2023) Article 2 pp. 1-23

On Solving Reachability in Grid Digraphs using a Pseudoseparator

by Rahul Jain and Raghunath Tewari

Received: January 13, 2020
Revised: May 25, 2022
Published: August 26, 2023

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

DOI: 10.4086/toc.2023.v019a002

© 2023 Rahul Jain and Raghunath Tewari
Licensed under a Creative Commons Attribution License (CC-BY)