On Solving Reachability in Grid Digraphs using a Pseudoseparator
Rahul Jain
Raghunath Tewari
Artikel in Zeitschriften
erschienen in:
Theory of Computing, Vol. 19, No. 2, pp. 1-23, 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(n1/2+ϵ) space. In 2018, the space complexity was improved to Õ(n1/3) by Ashida and Nakagawa (SoCG'18). In this paper, we show that there exists a polynomial-time algorithm that uses O(n1/4+ϵ) 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.

Theory of Computing
@article{v019a002, author = {Jain, Rahul and Tewari, Raghunath}, title = {On Solving Reachability in Grid Digraphs using a Pseudoseparator}, year = {2023}, pages = {1--23}, doi = {10.4086/toc.2023.v019a002}, publisher = {Theory of Computing}, journal = {Theory of Computing}, volume = {19}, number = {2}, URL = {}, }
Christoph Doppelbauer | 10.05.2024