Computing the Exact Distribution Function of the Stochastic Longest Path Length in a DAG

Abstract

Consider the longest path problem for directed acyclic graphs (DAGs), where a mutually independent random variable is associated with each of the edges as its edge length. Given a DAG G and any distributions that the random variables obey, let F _MAX(x) be the distribution function of the longest path length. We first represent F _MAX(x) by a repeated integral that involves n − 1 integrals, where n is the order of G. We next present an algorithm to symbolically execute the repeated integral, provided that the random variables obey the standard exponential distribution. Although there can be Ω(2ⁿ) paths in G, its running time is bounded by a polynomial in n, provided that k, the cardinality of the maximum anti-chain of the incidence graph of G, is bounded by a constant. We finally propose an algorithm that takes x and ε> 0 as inputs and approximates the value of repeated integral of x, assuming that the edge length distributions satisfy the following three natural conditions: (1) The length of each edge (v _i ,v _j ) ∈ E is non-negative, (2) the Taylor series of its distribution function F _ij (x) converges to F _ij (x), and (3) there is a constant σ that satisfies $\sigma^p \le \left|\left(\frac{d}{dx}\right)^p F_{ij}(x)\right|$ for any non-negative integer p. It runs in polynomial time in n, and its error is bounded by ε, when x, ε, σ and k can be regarded as constants.