Published by Dept. CS U. Chicago. Copyright 2010 CJTCS and the author.

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

• The article: PDF (209,417 bytes)
• Source materials: ZIP (53,500 bytes)
• Self citation in BIBTeX (306 bytes)
• Original version: PDF (177,288 bytes)

© 2010 Nutan Limaye, Meena Mahajan and Prajakta Nimbhorkar
Licensed under a Creative Commons Attribution License

Special Issue, CATS 2009, Article 4

Article 6

Special Issue

Published articles