An O(n~∈) Space and Polynomial Time Algorithm for Reachability in Directed Layered Planar Graphs

摘要

Given a graph G and two vertices s and t in it, graph reachability is the problem of checking whether there exists a path from s to t in G. We show that reachability in directed layered planar graphs can be decided in polynomial time and O(n~∈) space, for any ∈ > 0. The previous best known space bound for this problem with polynomial time was approximately O({the square root of}n) space [1]. Deciding graph reachability in SC is an important open question in complexity theory and in this paper we make progress towards resolving this question.