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

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

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

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.