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

摘要

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 Fmax(x) be the distribution function of the longest path length. We first represent Fmax(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~n) 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 Fij(x) converges to F_(ij)(x), and (3) there is a constant σ that satisfies σ~p ≤ | (d/dx)~P F_(ij){x)| 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.