A Counting-Based Approximation the Distribution Function of the Longest Path Length in Directed Acyclic Graphs

Abstract. We consider a stochastic version of the longest path problem in DAGs and propose an algorithm that ap-proximates the distribution function of the longest path length by utilizing (approximate) counting. In general, the stochastic longest path problem has several difficulties to solve; (1) we have no general method to calculate the exact distribution function FMAX(x) of the longest path length, and even if we could do that, (2) the distribution function often takes a complicated form. For this prob-lem, it is natural to consider calculating a simpler approx-imation of FMAX(x) and give a certain approximation guarantee. We show an algorithm that gives a bound on FMAX(x) by approximating ln jPj, whereP is the family of paths. The output of our algorithm A(a) satisfies that A(a) F1 MAX (a) for a 2jPj, and the approxima-tion factor is O((=) p C=h) for a 1=2, where and 2 are, respectively, the minimum mean and the maxi-mum variance of the edge lengths, C is an upper bound on ln jPj and h is the maximum number of edges in P 2 P. The running time of our algorithm is O(jEj), where jEj is the number of edges in a DAG