数理解析研究所講究録
第 1649 巻 2009 年 252-259

252

連続確率分布枝重み付き DAG に対する最長路長さ分布の計算
Computing the Distribution Function of the Stochastic Longest
Path Length in a DAG with Continuously Distributed Edge
Lengths
Ei Ando\dagger Hirotaka Ono\dagger \ddagger
Kunihiko Sadakane\dagger Masafumi Yamashita\dagger \ddagger\dagger Department of Computer Science and Communication Engineering,

Graduate School of Information Science and Electrical Engineering,
Kyushu University.
\ddagger Institute of Systems, Information Technologies and Nanotechnologies.
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. Givena DAG $G$ and any distributions that the random variables obey, let $F_{MAX}(x)$ be the distributionfunction of the longest path length. We first represent FMAX $(x)$ by a repeated integral that involves $n-1$ integrals, where 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 bepaths in $G$ , its running time is bounded by a polynomial in , provided that , 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 andas inputs
and approximates the value of repeated integral of , assuming that the edge length distributions
satisfy some natural conditions. : (1) The length of each edge $(v\iota, v_{j})\in E$ is non-negative, (2) the
Taylor series of its distribution function $F_{ij}(x)$ converges to $F_{:j}(x)$ , and (3) there is a constantthat satisfies
for any non-negative integer . It runs in polynomial time in ,and its error is bounded by , when $x,$
and can be regarded as constants.
$n$$\Omega(2^{n})$

$k$

$n$

$x$

$\epsilon>0$$x$$\sigma$$\sigma^{p}\leq|(\frac{d}{dx})^{p}F_{ij}(x)|$$\epsilon$1$p$$\epsilon,$$\sigma$$n$$k$Introduction

Let $G=(V, E)$ be a directed acyclic graph (DAG), where $V$ and $E$ are the sets of of vertices and $m$edges, respectively. Each edge
is associated with a random variable
representing its length.
Although the longest path problem for DAGs is solvable in linear time when edge lengths are constantvalues, the same problem with stochastic edge lengths is iormidable. Actually, there are at least two
different problem formulations; to find a path that has the highest probability of being the longest [12],or to compute the distribution function $F_{MAX}(x)$ of the longest path length [1-5, 7, 8, 10, 11]. In thispaper, we adopt thc second formulation.
The longest path problem in with uncertain edge lengths is known as the classic problems such as
Program Evaluation and Review Technique (PERT) [6] or Critical Path Planning (CPP) [9]. In these
problems, the lower and the upper bounds of the edge lengths (the activity duration) are given as
static values, and their goal is to obtain the lower and upper bounds on the longest path length in $G$ ,the duration of the whole project. However, we assume, in this paper, that edge lengths are randomvariables; we are not to determine the edge lengths but to cope with the resulting edge lengths thatrealize with some probability.
Delay analysis of logical circuits is a killer application of this problem, and besides Monte Carlosimulations, many heuristic approximation algorithms have been proposed so far (see e.g., [3, 5, 7]). They
run fast but their general drawback is that they do not have a theoretical approximation guarantee. To
theoretically guarantee an approximation ratio, some authors of this paper proposed an algorithm toconstruct a primitive function that approximates $F_{MAX}(x)[1,2]$ .
Computing the exact distribution function has also a long research history. Martin [11] proposed aseries-parallel reduction based method, assuming that each edge length obeys a polynomial distribution.
$n$$(v_{i}, v_{j})$$G$$X_{ij}$253
Kulkarni and Adlakha [10] proposed an algorithm that is based on the analysis of continuous time
Markov chain. Both algorithms unfortunately take an exponential time with respect to the graph size.
Indeed, when edge lengths obey discrete distributions, the problem is #P-complete [8], and is NP-hardcvcn for the series-parallel graphs [4].
We first show that $F_{MAX}(x)$ is represented by a repeated integral that involves $n-1$ integrals, for
any instance of the problem. The problem of computing $F_{MAX}(x)$ for any is thus reducible to the
problem of evaluating the repeated integral for . The evaluation of the repeated integral is possible bymaking use of standard numerical methods at the expense of accuracy and time.
In this paper, we pursuit the possibility of exact computation using the repeated integral. That
only $n-1$ integrals are involved might give us a chance to symbolically compute it in polynomial in ,although there can bepaths in(and the above NP-hardness results essential suggest that any
algorithm would need to evaluate each of thepaths).
Assuming that the random variables obey the standard exponential distribution, we show that there
is an algorithm to transform the repeated integral into a product of primitive functions. It runs inpolynomial time in , provided that , the cardinality of the maximum anti-chain of the incidence
graph of $G$ , is bounded by a constant.
We (of course) cannot present a polynomial time algorithm that works for any distribution of edge
length. Naive numerical methods to approximate the repeated integral, on the other hand, need sufficiently long computation time and do not guarantee approximation performance. We thus assume thatthe distribution function
associated with any edge
satisfies the following three natural conditions: (1) The length of each edge is positive i.e., $F_{ij}(x)=0$ for $x\leq 0),$ (2) there is a constant thatsatisfies
for any non-negative integer , and (3) the Taylor series of $F_{ij}(x)$ converges
to $F_{ij}(x)$ , and then present, for any, an approximation algorithm that evaluates $F_{MAX}(x)$ (i.e.,
the repeated integral) with an error less than . It runs in polynomial time in , when $x,$
and canbe regarded as constants.
This paper is organized as follows: After giving basic definitions and formulas in Section 2, we derive
the repeated integral form of $F_{MAX}(x)$ in Section 3. Section 4 is devoted to the first case in which anexact formula is derived assuming the standard exponential distribution, and Section 5 proposes anapproximation algorithm for the second case. Section 6 concludes this paper.
$x$

$x$

$n$

$G$

$\Omega(2^{n})$$\Omega(2^{n})$

$k$

$n$

$F_{ij}$$(v_{i}, v_{j})$$($$\sigma$$|( \frac{d}{dx})^{p}F_{ij}(x)$I$\leq\sigma^{p}$$p$$\epsilon>0$$n$$\epsilon$2$\epsilon,$$k$$\sigma$Preliminaries

Let $G=(V, E)$ be a directed acyclic graph with vertex set $V=\{v_{1}, v_{2}, \ldots , v_{n}\}$ and directed edge setof $m$ edges. We assume that each edge $(v_{i}, v_{j})\in E$ is associated with its lengththatis a random variable. A source (resp. terminal) of $G$ is a vertex in $V$ such that its in-degree (resp.
out-degree) is . We define the (directed) incidence graph of $G=(V, E)$ as a directed graph $G’$ withvertex set $V’=V\cup E$ and edge set $E’=\{(v_{i}, e), (e, v_{j})|e=(v_{i}, v_{j})\in E\}\subseteq(V\cross E)\cup(E\cross V)$ . We
denote the incidence graph of $G$ by $L(G)$ . A subset of $V$ is called an antichain of $G$ if each $v_{a}\in A$ is
not reachable from any other vertex $v_{b}\in A$ . If $(v_{i}, v_{j})\in E$ , two vertices andare neighbors to eachother, is a parent of , andis a child of . By $N(W)$ we denote the set of all neighbors of vertices
in $W$ . Let
be the set of all source-terminal paths. The longest path length $X_{MAX}$ of $G$ is given as$E\subseteq V\cross V$$X_{ij}$$0$$A$$v_{i}$$v_{i}$$v_{j}$$v_{j}$$v_{j}$$v_{j}$$\mathcal{P}$$X_{MAX}= \max_{\pi\in \mathcal{P}}\{\sum_{(v_{i},v_{j})\in\pi}X_{ij}\}$.

be a random variable. The probability $P(X\leq x)$ is called the (cumulative) distribution$X$ . The density
function of $X$ is the derivative of $P(X\leq x)$ with respect to . We say $X$
obeys the standard exponential distribution if the distribution function $P(X\leq x)$ is given by $P(X\leq$$x)=1-\exp(-x)$ if $x\geq 0$ and $P(X\leq x)=0$ if $x<0$ .
Letandbe two mutually independent random variables. Let $f_{1}(x)$ and $f_{2}(x)$ be the density, respectively. The sum $X_{1}+X_{2}$ is also a random variable whose distributionfunctions ofandfunction is given as
Let

$X$

function of$x$$X_{1}$$X_{2}$$X_{1}$$X_{2}$$P(X_{1}+X_{2} \leq x)=\int_{R}P(X_{1}+t\leq x|X_{2}=t)f_{2}(t)dt=\int_{R}F_{1}(x-t)f_{2}(t)dt$

,

(1)

254
wherc $F_{1}(x)$ and $F_{2}(x)$ are the distribution functions of, respectively. The distributionandfunction of $\max\{X_{1}, X_{2}\}$ is given as $P( \max\{X_{1}, X_{2}\}\leq x)=P(X_{1}\leq x\wedge X_{2}\leq x)=F_{1}(x)F_{2}(x)$.
$X_{2}$$X_{1}$

3

Repeated Integral Representation of $F_{MAX}(x)$In this section, we show that the distribution function $F_{1vIAX}(x)$ of the longest path length is represented
by a repeated integral that involves $n-1$ integrals. By definition,$F_{1vIAX}(x)=P(X_{MAX} \leq x)=P(\bigwedge_{\pi\in \mathcal{P}}(\sum_{e\in\pi}X_{c}\leq x))$.

(2)

Although this formula is compact, this fact does not directly implies an efficient computability, since
it would take into account all source-terminal paths in $G$ , which can be as many as. Next theorem
shows that $F_{h1AX}(x)$ is represented by a repeated integral that involves $n-1$ integrals. Thus $F_{MAX}(x)$can be computed by executing only $n-1$ integrals, which may be dramatically more efficient thanthe calculation of Eq. (2). Let $H(x)$ be a function that satisfies $H(x)=1$ if $x\geq 0$ and $H(x)=0$ if$x<0$ . Let $1(x)$ be a constant function that maps every to 1. Note that if $P(X\leq x)=H(x)$ (resp.
$P(X\leq x)=1(x))$ for any $x,$ $X$ is always equal to(resp.
).
$\Omega(2^{n})$

$x$

$0$

$-\infty$

Theorem 1. Let $G=(V, E)$ is a $DA$ G. Without loss of generality, we assume that $V=\{v_{1}, v_{2}, \ldots, v_{n}\}$is topologically ordered. For any edge $(v_{i}, v_{j})\in E$ , let $F_{1j}(x)$ be the distribution function thatobeys.
We associate a function $F_{ij}(x)\dot{w}th$ each edge
as follows: If
connec two sources or
two terminals, then $F_{1j}(x)=H(x)$ ; othenvise, $F_{ij}(x)=1(x)$ . Then the distribution function $F_{MAX}(x)$is given as$X_{ij}$$(v_{i}, v_{j})\not\in E$$ts$$(v_{i}, v_{j})$$P(X_{MAX} \leq x)=\int_{R^{n-1}}H(x-z_{1})\prod_{1\leq i\leq n-1}(\frac{d}{dz_{i}}\prod_{i+1\leq j\leq n}F_{ij}(z_{i}-z_{j}))dz_{i}$.

(3)Proof. Given a DAG $G=(V, E)$ , we first add edges as many as possible in such a way that the added

edges do not change the topological order. This yields a complete graph with acyclic orientations, which
is denoted by $\#_{n}=(V, E_{K})$ , where $E_{K}=\{(v_{i}, v_{j})|1\leq i<j\leq n\}$ . Notice thathas a uniquesourceand a unique terminal . For each of the edge $(v_{i}, v_{j})\in E_{K}$ , we associate a random variable, and assume thatthat represents the length ofobeys $F_{ij}(x)$ . We observe that $F_{MAX}(x)$$G$is exactly the same for $G$ and. Note that any path in is also a path in. Consider any pathin(of $G$ ) and a terminal
connecting a source(of $G$ ) that does not exist in $G$ . If contains
an edgesuch that $F_{ij}(x)=1(x)$ , then $\sum_{e\in\pi}X_{e}\leq x$ holds for all (see the note above
for intuition), which implies that such is ignorable in Eq. (2). Suppose that does not contain anedge
such that $F_{ij}(x)=1(x)$ . Let
is the path constructed from by removing all edges
connecting two sources or two terminals. Then
is a path connecting a source and a terminal in $G$ ,$X_{e}\leq x$ (see the note above for intuition).1 Thus $F_{MAX}(x)$ is exactly theand $\sum_{e\in\pi}X_{e}\leq x$ iff
same for $G$ and. In what follows, we assume $G=\vec{K}_{n}$ .
Define several notations:is the set of all paths fromtois the set of allpaths that do not pass a vertex in $U_{k}=\{v_{k}, v_{k+1}, \ldots, v_{n-1}\}$ , and $Z_{n-1}=X_{n-1,n}$ is the longest path
length from $v_{n-1}$ to the unique terminal. We would like to use $Z_{n-1}$ rather than $X_{n-1,n}$ inoforder to illustrate the transformations that should follow (5), but is not explicitly explained here for thelimitation of the space. Since $Z_{\iotaarrow 1}=X_{n-1,n}$ and’s are mutually independent, we have
$7_{n}$$v_{0}$$v_{n}$$X_{ij}$$(v_{i}, v_{j})$$X_{ij}$$\#_{n}$$\vec{K}_{n}$$\pi$$\#_{n}$$v_{S}$$v_{T}$$\pi$$(v_{i}, v_{j})\not\in E$

$x$

$\pi$

$\pi$

$\pi’$$(v_{i}, v_{j})\not\in E$$\pi$$\pi’$$\sum_{e\in\pi},$$- R_{n}$$\mathcal{P}(i,j)$$v_{i}$$v_{j},$$\mathcal{P}_{k}(i,j)$$v_{i}- v_{j}$$\vec{K}_{n}$$v_{n}$$X_{ij}$$P(X_{MAX} \leq x)=P(\bigwedge_{\pi\in \mathcal{P}_{n-1}(1.n)}(\sum X_{ij}\leq x)\bigwedge_{\pi\in \mathcal{P}}\bigwedge_{(1,,\iota-1)}(\sum X_{ij}+Z_{n-1}\leq x))$1

Several different paths
for $i=1,2,$$\pi_{1},$$\sum_{\epsilon\in\pi_{i}}X_{\epsilon}\leq x$$\pi_{2},$$\cdots$

$p$

.

(4)

may correspond to a single . Even in such a case, the AND of conditions, $X$
is reduced to condition.

$\cdots,$,.

$\pi’$$\pi\ell$$\sum_{\epsilon\in\pi}$$\leq x$

255
Let $G_{n-1}(x)=F_{n-1,n}(x)$ and $g_{n-1}(x)$ be the distribution function of $Z_{n-1}$ and its density function,
respectively. Sincc $dG_{n-1}(\tilde{k}n-1)=g_{n-1}(\tilde{4}n-1)d_{\tilde{4}}n-1$ , like the derivation of Eq.(l), by introducing an
integral, the right-hand side of Eq. (4) is represented as$\int_{R}P(_{\pi\in \mathcal{P}_{n-1(1,n)}}\underline{\underline{\backslash \wedge(}\sum_{(A)}X_{ij}\leq x)}\underline{\lrcorner}\bigwedge_{\pi\in \mathcal{P}}\underline{\underline{\backslash \bigwedge_{(1,n-1)}(\sum_{(B)}}X_{ij}+z_{n-1}\leq x)}_{\underline{Z}})dG_{n-1}(z_{narrow 1})$.

(5)

We then calculate the contribution of each edge by repeating the transformation of representing (andreplacing) the contribution by an integral. For $Z_{k}= \max_{k+1\leq l\leq n}\{X_{kl}+z_{l}\}$ , we divide the paths fromtointo two groups according to whether or not they pass . We then introduce one more integral toaggregate the probability that . takes a constant value . We can consider
as the dummy variableof a convolution. Note that $z_{n}=0$ by definition.2 Now for each of $Z_{n-1},$ $Z_{n-2},$, an integral has
been introduced with respect to , and (4) is transformed into$v_{1}$$v_{n}$$v_{k}$$Z_{l\prime}$$z_{k}$$z_{k}$$Z_{2}$$\ldots,$$z_{i}$$\int_{R^{n-2}}P(\bigwedge_{2\leq l\leq n\pi\in}\bigwedge_{\mathcal{P}_{2}(1,l)}(\sum X_{ij}+z_{l}\leq x)\bigwedge_{\pi\in}\bigwedge_{\mathcal{P}(1,2)}(\sum X_{ij}+\tilde{k}2\leq x))\prod G_{i}(z_{i}, \ldots, z_{narrow 1})dz_{i}$where$G_{i}(z_{i}, \ldots, z_{narrow 1})=\frac{d}{d_{\tilde{\sim}i}}\prod_{i+1\leq j\leq n}P(X_{ij}+z_{j}\leq\tilde{\sim}i)=\frac{d}{dz_{i}}\prod_{i+1\leq j\leq n}F_{ij}(\tilde{4}i-z_{j})$By definition, $\mathcal{P}(1,2)=\{(v_{1}, v_{2})\}$ and$\mathcal{P}_{2}(1, l)=\{(v_{1}, v_{l})\}$. Hence (6) is equal to,$G_{1}(z_{1}, \ldots, z_{n-1})=\prod_{2\leq\downarrow\leq n}F_{1l}(z_{1}-z_{l})$

.

di

(6)

.

(7)

$\int_{R^{n-2}}\prod_{2\leq l\leq n}F_{1l}(x-z_{l})\prod_{2\leq i\leq n-1}(\frac{d}{dz_{i}}\prod_{i+1\leq j\leq n}F_{ij}(z_{i}-z_{j}))dz_{i}$which implies the theorem by $\int_{R}H(x-z_{1})$,$G_{1}(z_{1,2}\tilde{k}, \ldots, z_{n-1})dz_{1}=G_{1}(x, z_{2,}z_{n-1})$

where
口

It is worth noting that Theorem 1 is applicable, even if the lengthof each edge
is a constantvalue. In this case, the step function $H(x-c_{ij})$ is given as the distribution function thatobeys. Let
be the (definite) longest path length fromto . Then the step function $F_{MAX}(x)=H(x-d_{1})$ is
obtained by Theorem 1.
In the following, we call dummy variable the corresponding variable of . Let $Q_{1}(z_{1}, z_{2}, \ldots, z_{narrow 1};x)=$$H(x-z_{1})$ and$(v_{i}, v_{j})$$c_{ij}$$X_{ij}$$d_{i}$$v_{n}$$v_{i}$$z_{i}$$v_{i}$$Q \downarrow+1(\sim\nu l+1, \ldots, z_{n-1};x)=\int_{R}Q_{l}(z_{l}, z_{l+1}, \ldots, z_{n-1};x)G_{l}(z\iota, z_{l+1}, \ldots, z_{n-1})dz_{l}$.

Theorem 1 states that we can calculate $Q_{n}(x)=F_{MAX}(x)$ by repeating integrals.

4

Exact Computation of the Repeated Integral

This section considers the case in which the edge lengths are given by mutually independent randomvariables that obey the standard exponential distribution function. We present an algorithm to computeeach ofsymbolically in this order by expanding the integrand into a sum of products
before calculating each integral. Let be the cardinality of the maximum anti-chain of $L(G)$ . By bounding the number of difFerent terins that can appear during the symbolic calculation, we show that its
running time is a polynomial in the size of , if is bounded by a constant.
2; if we define
Notice that we define
after
as the length of the longest path from$Q_{1},$ $Q_{2},$$\ldots,$$Q_{n}$$k$$G$$Z_{k}$

toto$v_{n}$

at a time, then$Y_{i}’ s$.

$Y_{i}$$z_{k+1},$ $z_{k+2},$$\ldots,$$k$$z_{n-1}$$Y_{l}$$v_{k}$’s are dependent on each other, which implies that the above proof cannot be applied

256
Proposition 1. $Let\uparrow/V_{i}=\{v_{j}|1\leq j\leq i\}$ . If
does not depend on .

$Q_{i}(z_{i}, \ldots, z_{n-1};x)$

Proof. Since$v_{l}\in W_{i}\backslash \{v_{i}\}$or $(u, v_{1})\not\in E$ for any $u\in W_{i}$ , then$z_{l}$

is a dummy variable of an integral if $l<i$ , it is obvious thatnever show up in
after the integrals are computed.
Suppose otherwise that $l>i$ . Then
N(Wi) T ノ . By Theorem 1, $G_{i}(z_{i}, \ldots, z_{n-1})$ does notdepend on .
口
$z_{l}$$z_{1}$$Q_{i}(z_{i,\ldots,\sim n-1}7;x)$$v\iota\not\in$$\backslash$$V_{i}$$z\iota$

Let $m=|E|,$ $n=|V|$ and$V_{i}$

be the set of children of$v_{i}$.

Theorem 2. Let $G=(V, E)$ be a $DAG$ such that the cardinality of the mavimum anti-chain of $L(G)$is at most . Assume that each random variable, which represents the length of edge
, obeys
the standard exponential distribution. Then the distributed function $F_{MAX}(x)$ of the longest path length$k$$X_{ij}$$(v_{i}, v_{j})$in $G$ is computable in $O((k+1)1n^{k+2}(2m+1)^{k+1})$ time.

Proof. We first show how we calculate $Q_{i+1}(z_{i+1,\ldots,n-1}\tilde{4};x)$ from $Q_{i}(z;x)$ by symbolically
executing the integral with respect to . For example, $Q_{3}(z_{3}, \ldots, z_{n-1};x)$ is given by$z_{i}$.

$Q_{3}(z_{3}, \ldots, z_{n-1};x)=\int_{R}\gamma$(8)

Since $H(x)=0$ for all $x<0,$ $Q_{3}(z_{3,\ldots,.n}\tilde{4}-1;x)=0$ if $x<0$ . When $x\geq 0$ , since $H(x)=1$ ,$Q_{3}(z_{3}, \ldots, z_{n-1};x)=\int_{a}^{b}\prod_{v_{j}\in V_{1}}$$($l–exp $(-(x-z_{j}))) \frac{d}{dz_{2}}\prod_{v_{l}\in V_{2}}(1-\exp(-(z_{2}-z_{l}))))dz_{2}$ ,

(9)

wherc
and $b=x$ , since otherwise the contribution to the integral becomes becauseof the effect of $H$ . Since each of ’s can take the maximum, at mostdifferent formulas appear,
corresponding to different $a=z_{l}$ , as possible results of $Q_{3}(z_{3}, \ldots, z_{n-1};x)$ . Onceis fixed to a ,executing symbolic integration of the right-hand side of Eq. (9) is easy, since possible terms appearing
in the integrand have a form of $c_{1}\exp(-c_{2}z_{2})$ for some constantand . In general, we can derive$Q_{i+1}(z_{i+1}, \ldots, z_{n-1};x)homQ_{i}(\sim..z;x)$ in the same way.
To estimate the time complexity of the algorithm, let us estimate the number of terms that are possible to appear in the execution. By Proposition 1, the number of variables appeared in $Q_{i}(z_{i}, \ldots, z_{n-1};x)$is at most $k+1$ for any . As explained, to obtain, we need to consider at most $k+1$
different cases corresponding to different $a=z\iota$ . It is easy to see that to obtain $Q_{4}(z_{4}, \ldots, z_{n-1};x)$ , foreach of the cases for, we need to consider at most different cases. Although this leads to that there
may be $O(k^{i})$ cases for
depends is at most $k+1$ by
in general, the number of variables on which
Proposition 1, which implies that, in general in, there can be no more than $(k+1)!$ distinct cases.
To complete the proof, we show that at most $n^{k+1}(2m+1)^{k+1}$ terms are possible to appear, for each of
at most $(k+1)!$ cases.
Let us consider the number of the terms in the integrand in each case. Since it is easy to see that$\exp(\beta_{0}x)$ andeach term is a product of, where’s and ’s are integers, we boundthe number of terms by the number of possible terms. By the form of Theorem 1, we can see that the
maximum degrees ofand that appear in the terms in $Q_{i}(z_{i}, \ldots, z_{n-1};x)G_{i}(z_{i}, \ldots, z_{n-1})$ of eachcase can only increase by one in one integral and hence ’s are non-negative integer and less than .
Similarly, we can also see that the degrees ’s of $\exp(z_{j})$ ’s and $\exp(x)$ can only increase or decrease by
one in a multiplication of two distribution functions and hence ’s are integers between $-m$ and $m$ .
Therefore, the integrand in each cases consists of at most $n^{k+1}(2m+1)^{k+1}$ terms, which amounts to thatthe calculation of each $Q_{i+1}$ $(z_{i+1}, \ldots , z_{n-1};x)$ from $Q_{i}(z_{i}, \ldots, z_{n-1};x)$ takes $O((k+1)!n^{k+1}(2m+1)^{k+1})$
time.
口
$0$

$a= \max_{v_{\ell}\in V_{2}}z_{\ell}$$|V_{2}|$$z_{l}$$a$$c_{1}$$i$$z_{l}$$c_{2}$$Q_{3}(\wedge\sim_{3}, \ldots, z_{n-1};x)$$k$$Q_{3}$$Q_{i}$$Q_{i}$$Q_{i}$$x^{\alpha_{0}},$$\tilde{4}j^{S}$$\exp(\beta_{j}z_{j})$$z_{j}^{\alpha_{j}},$$\alpha_{j}$$\beta_{j}$

$x$

$n$

$\alpha_{j}$$\beta_{j}$$\beta_{j}$Corollary 1. A closed form of $F_{MAX}(x)$ consisting of pnmitive functions is obtained in polynomial time
if is bounded by a constant, provided that the edge lengths obey the standard exponential tribution.
$k$$d\dot{u}$2575Approximation of the Repeated Integral

In this section, we assume that the cardinality of the incidence graph $L(G)$ of a given DAG $G$ isbounded by a constant . We show that the distribution function $F_{MAX}(x)$ of the longest path lengths
can be approximately calculated in polynomial time in , if the length of each edge $(v_{i}, v_{j})\in E$ is nonnegative and the Taylor series of its distribution function $F_{ij}(x)$ converges to $F_{ij}(x)$ . Here by Taylor
polynomial of, we mean the Taylor polynomial that is generated by $f(z_{1}, \ldots, z_{n};x)$ at$x=z_{1}=\tilde{k}2=\ldots=z_{n}=0$ .
We must be careful for the order of computing the Taylor polynomial of the repeated integral thatis shown in Theorem 1. Let be the order of the Taylor polynomial. The most intuitive idea is that wecomputc the Taylor polynomial of the whole integrand
$k$

$n$

$f(z_{1,\ldots,\tilde{\sim}n};x)$$p$$H(x-z_{1}) \prod_{1\leq i\leq n-1}\frac{d}{dz_{i}}\prod_{i+1\leq j\leq n}F_{ij}(z_{i}-z_{j})$

,

(10)

treating it as a function of variables $(i.e., x, z_{1}, z_{2}, \ldots, z_{n-1})$ . However, this intuitive way of computing
the Taylor polynomial is not efficient for obtaining the value of $F_{MAX}(x)$ with an error less than ; therunning time may be more than exponential with respect to the size of $G$ even if is a constant. Let
us describe thederivatives of (10) as a sum of products of $F_{ij}(z_{i}-z_{j})$ or its derivatives of someorder. Since one differentiating operation of (10) or its derivatives creates $2k$ times as many terms asin the original if we do not replace the distribution functions $F_{ij}(x)$ by particular definition of the edge
lengths’ distribution functions, there may be $O((2k)^{p})$ terms in thederivative of (10). Then, it can
bc shown that the order of the Taylor polynomial needs to be almost linear to the size of the given
DAG $G$ to keep the error less than a constant even if is a constant, which implies that the running
time may be more than exponential of $m$ and .
In order to lower the running time, we approximate $Q_{i}(z_{i}, \ldots, z_{n-1};x)$ by $A_{i}^{p}(z_{i}, \ldots, z_{n-1};x)$ thatis computed by the following procedures: (1) $A_{2}^{p}(z_{2}, \ldots, z_{n-1};x)$ is the Taylor polynomial of order
generated by $Q_{2}(z_{2}, . , . , z_{n-1};x)= \prod_{v\cdot\in V_{1}}F_{1j}(x-z_{j})$ , and (2) $A_{i}^{p}(z_{i}, \ldots, z_{n-1};x)$ is the Taylor
polynomial of order generated by$n$$\epsilon$$k$$p\cdot th$$parrow th$$p$$\epsilon$

$k$

$n$

$p$

$J$

$p$

$\int_{R}A_{i-1}^{p}(z_{i-1}, \ldots, z_{n-1};x)G_{i-1}(z_{i-1,\ldots,n-1}\tilde{4})dz_{iarrow 1}$

.

(11)

This integral can be calculated using integration by parts, which yields a sum of products of polynomials
and some anti-derivatives of $G_{i-1}(z_{i-1,\ldots,\tilde{\sim}n-1})= \prod_{i\leq j\leq n}F_{i-1,j}(z_{i-1}-\tilde{\sim}j)$ . The procedure (2) canbe repeated for $i=3,4,$.
Since all edge lengths are non-negative by assumption, the anti-derivative of $G_{i-1}(z_{i-1,\ldots,\tilde{\sim}n-1})$of positive order is equal to at the origin $x=z_{i}=z_{i+1}=\cdots=z_{n-1}=0$ , which allows us tocompute$(z_{i}, \ldots , z_{n-1};x)$ as the Taylor polynomial oforder without knowing the analytic form of
the anti-derivatives.
In the next theorem, we show that the time to computewhere is large enough to keep theerror less than is polynomial of the size of $G$ , assuming that $x,$ and the maximum size of an antichain
in $L(G)$ is a constant. We also assume the existence of a constant , that satisfies
for any non-negative integer and any edge $(v_{i}, v_{j})\in E$ .
Notice that must be bounded by a constant for the assumption that is bounded by a constant.
If there is an algorithm $A$ that gives the value of $F_{MAX}(x)$ in the same time regardless of , we canconsider “compressed edge length” $X_{e}^{l}=X_{e}/s$ , whereis the length of and $s\geq 1$ . Then we candefine the “compressed” distribution functions $F_{MAX}’(x)=P( \bigwedge_{\pi\in \mathcal{P}}(\sum_{e\in n}X_{e}’\leq x))$ of the longest path
length. Since $F_{MAX}’(x)=F_{MAX}(sx)$ , the value of $F_{MAX}(sx)$ can be obtained for any in the samerunning time, which can be used for obtaining the value of $F_{MAX}(x)$ for arbitrary . Therefore, it isessential to bound by a constant as well as .
$\ldots,$

$n$

$0$

$A_{i}$$p$$G_{i-1}(z_{iarrow 1}, \ldots, z_{n})$$A_{n}^{p}(x)$

$p$

$k$

$\epsilon$$\epsilon$$\sigma^{p}\geq|(\frac{d}{dx})^{p}F_{ij}(x)|$$\sigma$$p$$\sigma$$x$$\sigma$$X_{e}$

$e$

$s$

$x$

$x$

$\sigma$

Theorem 3. Let $G=(V, E)$ be a $DAG$ and assume that the cardinality of the anti- chain of its incidence
graph $L(G)$ is at most . Let $F_{ij}(x)$ be the distribution function of the length of an edge
that
$k$

$(v_{i}, v_{j})$258
is defined in Theorem 2. Let be a value such that $\sigma^{p}\geq|(_{Tx}d)^{p}(F_{ij}(x))|$ for any non-negative integer
and any edge $(i, j)\in$ E. We further assume that the Taylor senes of $F_{ij}(x)$ converges to $F_{ij}(x)$itself and that the time complexity of computing the p-th derivative of $F_{ij}(x)$ is $0(cxp(p))$ . Thensuch that $|A_{n}^{\rho}(x)-F_{MAX}(x)|\leq\epsilon$ holds is calculated in time $O((k+1)!(p+1)^{k}k^{P+1}\exp(p))$ , where$\sigma$$p$$A_{n}^{p}(x)$$p=O(k^{2}x\sigma+\ln n+\ln 1/\epsilon)$.

Proof. By the similar argument in the previous section, it can be shown that the time to computeis $O((k+1)!n(p+1)^{k}k^{p+1}\exp(p))$ . We have $O((k+1)!)$ cases for computing integral of $A_{i}^{p}(z_{i}, \ldots, z_{n-1};x)$ .
In each cases, the integrand is the sum of products
over all possible,
whereis the corresponding variable of the j-th vertex in(i.e.,
is equal to one of, where $W_{i}=\{v_{1}, \ldots, v_{i}\}$ . Since
whereis a non-negative integer at most ,the number of the terms in each case of integral is at most $(p+1)^{k}$ . Since differentiating a term in
the resulting form of (11) times with respect to one ofcreates at mosttermsthat consist of at most dummy variables as the factors each, the total running time of computing
as the Taylor polynomial is at most $O((k+1)1(p+1)^{k}k^{p+1})$ . Since, by assumption,
the time complexity of computing p-th derivative of $F_{ij}(x)$ is $O(\exp(p))$ , the running time of computing
is $O((k+1)!n(p+1)^{k}k^{p+1}\exp(p))$ .
Now we concentrate on proving that $p=O(k^{2}x\sigma+\ln n+\ln 1/\epsilon)$ is sufficient for satis ing $|A_{n}^{p}(x)-$$F_{1vIAX}(x)|\leq\epsilon$ . For each edge
, we consider a random variable $X_{ij}’=X_{ij}/(k\sigma)$ . Let $F_{MAX}’(x)$ be
the distribution function of the longest path length which is defined for the case where edge lengths are
given as. Since $F_{MAX}(x)=F_{MAX}’(k\sigma x)$ , we consider the normalized edge length
instead ofand the normalized distribution function $F_{1vIAX}’(x)$ instead ofand $F_{MAX}(x)$ in the following. For thesimplicity, we give the proof for the case $\sigma=1/k$ . The proof for the general can be given by replacingin the following by.
Let
be the difference between $A_{i}^{p}(z_{i,}z_{n};x)$ and $Q_{i}(z_{i}, \ldots, z_{n-1};x)$ . We first bound the errorthat is created when the Taylor polynomial of $Q_{2}(z_{2}, \ldots, z_{n-1};x)$ is computed. By generalizing the$A_{?}^{p}(x)$$\alpha=\{\alpha_{1}, \ldots, \alpha k\}$$C( \alpha)\prod_{v_{j}\in V_{l}}y_{j}^{\alpha_{j}}$$N(W_{i})\backslash W_{i}$$y_{j}$$v_{h}\in N(W_{i})\backslash T^{1}V_{i})$$z_{h}$$y_{j}$$p$$\alpha_{j}$$p$$z_{i+1},$ $\ldots,$$k^{p}$$z_{narrow 1},$ $x$$k$$A_{i}^{p}(\tilde{z}i, \ldots, z_{narrow 1};x)$$A_{n}^{p}(x)$$\mathfrak{h}r$$(v_{i}, v_{j})$$X_{ij}$$X_{ij}’$$X_{ij}’$$X_{ij}$$\sigma$$kx\sigma$$x$$\epsilon_{i}$$M( \sum_{v_{j}\in V_{2}}z_{j})^{p+1}$

evaluation of the Taylor polynomials in [13], it is easy to show that $|\epsilon 2|\leq\overline{(p+1)!}$ whereis an upper bound on the $(p+1)$ -th derivatives of $Q_{2}(z_{2}, \ldots, z_{n-1};x)=\prod_{2<j<n}F_{1j}(x-z_{j})$ at theorigin where $z_{2}=Z_{3}=\cdots=z_{narrow 1}=x=0$. By the above normalization, it is
to show that $M$ isless than 1. Since the dummy variables$z_{n-1}$ of integrals are non-negative and less than
, by
Proposition 1, wc have$M$$\overline{e}as^{-}y$$z_{1},$$x$$\ldots,$$| \epsilon_{2}|\leq\frac{(xk)^{\rho+1}}{(p+1)!}$

.

(12)

Let us bound the error that is created when $A_{i+1}^{p}(z_{i+1}, \ldots, z_{n-1};x)$ is computed as the Taylor
polynomial of the convolution of
and $\prod_{i+1\leq j\leq n-1}F_{ij}(z_{i}-z_{j})$ with respect to . By
dcfinition, we have$A_{i}^{p}(z_{i}, \ldots, z_{n-1};x)$$z_{i}$$\epsilon_{i+1}=A_{i+1}^{p}(z_{i+1}, \ldots, z_{n-1};x)-\int_{R}(A_{i}^{p}(z_{i}, \ldots, z_{n-1};x)+\epsilon_{i})G_{i}(z_{i}, \ldots, z_{n-1})dz_{i}$Since $A_{i+1}^{\rho}(z_{i+1}, \ldots, z_{n-1};x)$ is the Taylor polynomial of
have$\int_{R}A_{i}^{p}(z_{i,\ldots,n}\tilde{k}-1;x)G_{i}(z_{i}, .

$| \epsilon_{i+1}|\leq\frac{(kx)^{p+1}}{(p+1)!}+\int_{R}|\epsilon_{i}|\frac{d}{d_{\tilde{k}}i}\prod_{i+1\leq j\leq narrow 1}F_{ij}(z_{i}-z_{j})dz_{i}=\frac{(kx)^{p+1}}{(p+1)!}+|\epsilon_{i}|$This leads to$| \epsilon_{n}|\leq(n-1)\frac{(kx)^{p+1}}{(p+1)!}$by (12) and (14) for $i=2,3,$$\ldots,$

$n$

.

.

, , z_{narrow 1})dz_{i}$

.

(13)
, we
(14)

.

converges to very quickly. If $kx>1,$ $p=O(\ln(n-1)+kx+\ln 1/\epsilon)$ is, the error
Ifsufficient to have $|\epsilon_{n}|=|A_{n}^{p}(x)-Q_{n}(x)|$ less than .
口$kx\leq 1$$0$$\epsilon_{n}$$\epsilon$

We immediately obtain the following corollary.
Corollary 2. If $x,$
andare constants, the proposed algorithm computes the value of $F_{MAX}(x)$urithin error in a polynomial time of the size of .
$\epsilon,$$\epsilon$$k$$\sigma$

$G$

259
6

Conclusion

In this paper, we have investigated the longest path problem for DAGs $G,$ where the edge lengths are
given as mutually independent random variables. We have shown that the distribution function $F_{MAX}(x)$of the longest path length is given as a form of repeated integral that involves $n-1$ integrals, whereis the order of $G$ . We can thus approximately evaluate $F_{1vIAX}(x)$ for any fixed by applying numericalmethods to the form, at the expense of accuracy and time.
We however suggest that an important application of the repeated integral is in symbolic computation
of $F_{MAX}(x)$ . Because only $n-1$ integrals are involved with, it may give us a chance to symbolicallycompute it in polynomial in , although there arepaths in $G$ In fact, we have shown that a
representation of $F_{MAX}(x)$ by a combination of primitive functions is obtained in $O((k+1)!n^{k+2}(2m+$$1)^{k+1})$ time, provided
that the edge lengths obey the standard exponential distribution, where is the
maximum anti-chain cardinality of the incidence graph $L(G)$ . Recall that the problem is NP-hard evenfor series-parallel graphs when the edge lengths obey discrete distributions. A natural open questionis thus to find another class of distribution functions for which there is a polynomial algorithm tosymbolically execute the repeated form.
Since naive iiumerical metbods to approximate the repeated integral need sufficiently long time anddo not have performance guarantees, by making use of the Taylor polynomials, we have proposed an
approximation algorithm to compute $F_{MAX}(x)$ with error smaller than for any given and , assumingthat thc distributions that the edge lengths obey satisfy the following three natural conditions; 1)
F. $(x)=0$ for $x\leq 0,2$ ) the Taylor series of $F_{e}(x)$ converges to $F_{e}(x)$ itself, and 3) for any non-negative
integer , there is a constant satisfying $\sigma^{p}\geq|(zi|t)^{p}F_{e}(x)|$ . It takes a polynomial time in , wheneach of $k,$ $x,$ and can be regarded as constants.
$n$

$x$

$n$

$\Omega(2^{n})$.

$k$$\epsilon$$p$$\sigma$$x$$\epsilon$$n$$\sigma$$\epsilon$

References
1. E. Ando, T. Nakata, M. Yamashita, Approximating the longest path length of a stochastic DAG by anormal distribution in linear time, Joumal of Discrete Algorithms (2009), doi $:10.1016/j.jda$ .2009.01.001
2. E. Ando, H. Ono, K. Sadakane, M. Yamashita, A Generic Algorithm for Approximately Solving Stochastic
Graph optimization Problems, submitted for publication.
3. E. Ando, M. Yamashita, T. Nakata, Y. Matsunaga, The Statistical Longest Path Problem and Its Application to Delay Analysis of Logical Circuits, proc.TAU, 2002, pp. 134-139.
4. M. O. Ball, C. J. Colboum, and J. S. Proban, Network Reliability, Handbooks in Operations Researchaiid Management Science, Vo17: Network Models, M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L.
Nemhauser eds.), Elsevier Science B. V. (1995) 673-762.
5. M. Berkelaar, Statistical delay calculation, a linear time method. Proceedings of the Intemational Workshop on Timing Analysis $(TA U’ 97)$ , 1997, pp. 15-24,
6. C. E. Clark, The PERT model for the distribution of an activity time, Operations Research 10 (1962)$($

405-406.
7. M. Hashimoto and H. Onodera, A performance optimization method by gate sizing using statistical static
timing analysis. IEICE Tmns. thndamentals, E83-A, 12, 2000, pp. 2558-2568.
8. J. N. Hagstrom, Computational Complexity of PERT Problems, NETWORKS, Vol. 18, 1988, pp. 139-147.
9. J. E. Kelley, Jr., Critical-path plazming and scheduling: Mathematical basis, Opemtions Research 10 (1962)
912-915.
10. V. G. Kulkarni and V. G. Adlakha, Markov and Markov-Regenerative PERT Networks, Operations Research, Vol. 34, 1986, pp. 769-781.
11. J. J. Martin, Distribution of the time through a directed, acyclic network, Operations Research Vol. 13,
1965, pp. 46-66.
12. E. Nikolova, Stochastic Shortest Paths Via Quasi-convex Maximization, Proceedings of 14th Annual European Symposium on Algo 短仇$ms$ (ESA2006), LNCS 4168, 2006, pp.552-563.
13. G. B. Thomas,Jr., Thomas’ Calculus Intemational Edition, Pearson Education, 2005, pp965-1066.