Search Results

One of the central questions in space complexity is whether nondeterministic logspace computations (NL) can be simulated in unambiguous logspace (UL). A stronger notion, reach unambiguity (ReachUL ⊆ UL ∩ coUL), requires every configuration reachable from the start to have exactly one computation path [Buntrock et al., 1991]. It is known that directed graph reachability is NL-complete, planar graph reachability is in UL, and undirected graph reachability is in deterministic logspace (L). In this work, we study the space complexity of reachability problem for restricted directed graph families and show the following. 1) For reach unambiguous graphs (graphs with at most one path from start vertex to every vertex), [Lange, 1997] showed that reachability is in ReachUL. As our main result, we show that for simple path graphs (introduced in [Kannan et al., 2008], which contains reach unambiguous graphs), where each vertex has at most one simple path from the start, the reachability problem lies in UL ∩ coUL. The key difficulty lies in recognizing whether the input graph is a simple path graph or not. 2) Our first result can also be equivalently stated as follows: the recognition problem for simple path graphs is in UL ∩ coUL if and only if the reachability problem restricted to simple path graphs is also in UL ∩ coUL. Inspired by this, we investigate the complexity of graph recognition versus graph reachability for other directed 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 ReachUL-complete).