Paper Info
Title
Longest paths in planar DAGs in unambiguous logspace
Abstract
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.
Year
Venue
Keywords
2009
Clinical Orthopaedics and Related Research
directed acyclic graphs,total number,distinct path,shortest path,longest path,distance computation,general graph,reachability,planar graph,planar,general dags,polynomial time,planar dags,unambiguous logspace,directed acyclic graph
DocType
Volume
Citations 
Conference
abs/0802.1699
6
PageRank 
References 
Authors
0.53
12
3
Name
Order
Citations
PageRank
Nutan Limaye113420.59
Meena Mahajan268856.90
Prajakta Nimbhorkar317015.04