Longest Paths in Planar DAGs in Unambiguous Logspace

Limaye, N., Mahajan, M. and Nimbhorkar, P.

Reachability and distance computation are known to be NL-complete in general graphs, but within UL ? co-UL if the graphs are planar. However, finding longest paths is known to be NP-complete, even for planar graphs. We show that with the combination of planarity and acyclicity, finding the length of the longest path (and also enumerating one such path) is also in UL ? co-UL. The result extends to toroidal DAGs as well. We also address the question of when reachability, distance, and longest path are indeed equivalent on DAGs, and give partial bounds. When the number of distinct paths is bounded by a polynomial, counting the number of paths is known to be in NL. We show that for planar DAGs with this promise, counting can be done by a UAuxPDA in polynomial time. The UAuxPDA(poly) 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 in general DAGs is possible in LogDCFL provided the number of paths is bounded by a polynomial and the target node is the only sink.