Longest paths in planar dags in unambiguous logspace

Abstract

We present a transformation from longest paths to shortest paths in sub-classes of directed acyclic graphs (DAGs). The transformation needs log-space and oracle access to reachability in the same class of graphs. As a corollary, we obtain our main result: Longest Paths in planar DAGs is in UL ∩ co-UL. The result also extends to toroidal DAGs. Further, we show that Longest Paths in max-unique DAGs where the target node is the unique sink is in UL ∩ co-UL. We show that for planar DAGs with the promise that the number of distinct paths is bounded by a polynomial, counting paths can be done by an unambiguous pushdown automaton equipped with an auxiliary log-space worktape and running in polynomial time. This bound also holds if we want to compute the number of longest paths, or shortest paths, and this number is bounded by a polynomial (irrespective of the total number of paths). Along the way, we show that counting paths in general DAGs can be done by a deterministic pushdown automaton with an auxiliary log-space worktape and running in polynomial time, and hence is in the complexity class LogDCFL, provided the number of paths is bounded by a polynomial and the target node is the only sink.