Space complexity advances for reachability in simple path directed graphs
Space Complexity of Reachability in Simple Path Graphs
Computational Complexity
Summary
This paper looks at a problem called the reachability problem in computer science, which is about checking if there is a path from one point to another in a network. The researchers studied special types of networks called simple path graphs, where each point can be reached by only one unique route. They showed that deciding if a point is reachable can be done using very little memory, improving on previous knowledge about related graphs. They also connected this problem with figuring out whether a network itself fits into this special category.
What this means in practice
- •For software engineers: Design memory-efficient algorithms for verifying paths in restricted directed networks during debugging or static analysis.
- •For database system developers: Optimize query evaluation in graph databases when queries involve checking reachability in specialized graph structures with unique path properties.
A theory result. No direct application yet.
Authors
Krishnamoorthy Dinesh, Chandana Sasidharan
Abstract
One of the central questions in space complexity is whether nondeterministic logspace computations ($\textsf{NL}$) can be simulated in unambiguous logspace ($\textsf{UL}$). A stronger notion, \emph{reach unambiguity} ($\textsf{RUL} \subseteq \textsf{UL} \cap \textsf{co}\textsf{UL}$), requires every configuration reachable from the start to have exactly one computation path (Buntrock et.al. 91). While directed graph reachability is $\textsf{NL}$-complete, planar graph reachability is in $\textsf{UL}$ and undirected graph reachability is in deterministic logspace ($\textsf{L}$). In this work, we study the space complexity of reachability problem for restricted directed graph families and show the following. - For reach unambiguous graphs (graphs with at most one path from start vertex to every vertex), Lange (Lange 97) showed that reachability is in $\textsf{RUL}$. As our main result, we show that for simple path graphs (introduced in Kannan et.al. 08), which contains reach unambiguous graphs), where each vertex has at most one simple path from the start, we show that the reachability problem lies in $\textsf{UL} \cap \textsf{co}\textsf{UL}$. - Our first result can also be equivalently stated as: the recognition problem for simple path is in $\textsf{UL} \cap \textsf{co}\textsf{UL}$ if and only if the reachability problem restricted to simple path graphs is also in $\textsf{UL} \cap \textsf{co}\textsf{UL}$. Inspired by this, we investigate the complexity of graph recognition versus graph reachability for graph classes. Observe that for any graph class, solving reachability (for the class) also solves the recognition problem for that class. We show that for reach unambiguous graphs, solving recognition is as hard as solving reachability (making both of them $\textsf{RUL}$-complete). (Abstract shortened to meet arXiv limits)