FIT2008（第7回情報科学技術フォーラム）RA-003

A Counting-Based Approximation the Distribution Function of the Longest
Path Length in Directed Acyclic Graphs
Ei Ando, Hirotaka Ono, Kunihiko Sadakane and Masafumi Yamashita
Dept. Computer Sci. and Communication Eng., Kyushu University, 744 Motooka, Nishi-ku, Fukuoka, Fukuoka 819-0395, Japan.
Abstract. We consider a stochastic version of the longest
path problem in DAGs and propose an algorithm that approximates the distribution function of the longest path
length by utilizing (approximate) counting. In general, thestochastic longest path problem has several difficulties tosolve; (1) we have no general method to calculate theexact distribution function FMAX (x) of the longest path
length, and even if we could do that, (2) the distributionfunction often takes a complicated form. For this problem, it is natural to consider calculating a simpler approximation of FMAX (x) and give a certain approximation
guarantee. We show an algorithm that gives a bound on
FMAX (x) by approximating ln |P|, where P is the familyof paths. The output of our algorithm A(a) satisfies that−1A(a) ≥ FMAX(a) forpa ≥ 2−|P| , and the approximation factor is O((σ/µ) C/h) for a ≥ 1/2, where µ andσ 2 are, respectively, the minimum mean and the maximum variance of the edge lengths, C is an upper bound on
ln |P| and h is the maximum number of edges in P ∈ P.
The running time of our algorithm is O(|E|), where |E|
is the number of edges in a DAG.

1 Introduction
1.1

Problem and Results

We consider a stochastic version of the longest path
problem in DAGs and propose an algorithm that approximates the distribution function of the longest path
length by utilizing approximate counting. Let G =(V, E) be a directed graph and each edge e ∈ E isassociated with an edge length Xe . InPthe longest path
problem, we are to obtain maxP ∈P { e∈P Xe } whereP ⊆ 2E is the family of paths in G. In a stochastic
version of the longest path problem, each edge length
is given as a random variable. Then the longest path
length of the problem is also a random variable. Weconsider the P
problem to find the distribution functionof maxP ∈P { e∈P Xe }. In this paper, we assume thatthe edge lengths are mutually independent and normally distributed. Although we deal with the longest
path problem in this paper for simplicity, we can construct a similar algorithm for the shortest path problem
by calculating the complementary distribution functions instead of the distribution functions.
Let FMAX (x) be the distribution function of thelongest path length. Then a stochastic version of thelongest path problem is to calculate distribution function FMAX (x). In general, the stochastic longest path
problem has several difficulties to solve; (1) we haveno general method to calculate the exact distributionfunction FMAX (x), and even if we could do that, (2)the distribution function often takes a complicated form.
For these problems, it is natural to consider calculating a simpler approximation of FMAX (x) and give acertain approximation guarantee. There are roughly
two standpoints of approximating a function by another function: (1) fitting: find a function that minimizes “errors” from the original function by adjusting
its parameters and (2) bounding: find upper and lower
bounds on the original function such that each of themis as close to the other as possible. In this paper, wetake the latter standpoint to figure out the behaviourof FMAX (x). A half of the problem, obtaining an upper bound on FMAX (x), can be easily
Psolved, because
the distribution function FP (x) of e∈P Xe for any
P ∈ P is an upper bound on FMAX (x). However theother half of the problem, obtaining a lower bound on
FMAX (x), is not trivial. Hence we concentrate on obtaining a lower bound on FMAX (x).
In this paper, we show an approximation algorithm
that gives a function by utilizing an upper bound C onln |P| and the function bounds FMAX (x) from below.
The output A(a) of our algorithm satisfies A(a) ≥−1
FMAX(a) for ap≥ 2−|P | , and the approximation factor is O((σ/µ) C/h) for a ≥ 1/2, where µ and σ 2
are, respectively, the minimum mean and the maximum variance of the edge lengths, and h is the maximum number of edges in a path in G. The running
time of our algorithm is O(|E|).
1.2Related Work

The stochastic longest path problem has been extensively investigated, since there are many useful applications. The (deterministic) longest path problem on
DAGs are known as PERT [8] in the fields of scheduling and Operations Research, and their stochastic versions are considered from 1960s [4, 7, 6]. The problem

7（第1分冊）FIT2008（第7回情報科学技術フォーラム）is also intensively studied from the viewpoint of circuit delay analysis [2, 3, 5, 9]. They approximate thedistribution function of the longest path length in heuristic ways.They run practically fast, but have no guarantee about the approximation. Then authors of thispaper proposed an algorithm that approximates thelongest path length from below with approximation
guarantee [1].

2 Preliminaries
Let X be a random variable with mean µ and varianceσ 2 . A random variable X obeys a normal distribution
N (µ, σ 2 ) if its distribution function is given as, !
Z x
1 t−µ 21
√ exp −dt.
P (X ≤ x) =2σ−∞ σ 2π

3 Approximation Algorithm

where C is an upper bound on |P|. If C = ln |P|, we2 ).
have A(a) = L(a1/|P| ; µmax , σmax
The time complexity of our algorithm is O(|E|).
It is well known that we can calculate µ max and σmaxin O(|E|) time using the technique of PERT [8]. Since
we can easily show that 2|V | is an upper bound on thenumber of paths in a DAG, one can take ln 2 |V | as thevalue of C. This takes only O(log |V |) time.
As for the approximation factor, we can prove thefollowing theorem.
Theorem 1. The approximation factor of the algorithm
is given byr !
A(a)
σ C,
=O−1µ hFMAX(a)where µ = mine∈E {µe }, σ = maxe∈E {σe }, and h isthe maximum number of edges in P ∈ P.
This theorem shows a trade-off between the approximation factor and the computational time; we canhave better approximation factor by taking the exact
Xe , the lengthµ max =P of edge e ∈2E. Suppose thatP2maxP ∈P { e∈P µe } and σmax = maxP ∈P { e∈P σe } ln |P| as the value of C, which may increase the comare known. Then consider the distribution function F B (x) putational time.
2 ). We can prove that (F (x))|P| is aof N (µmax , σmaxBlower bound on FMAX (x) for x ≥ µmax . In order toReferences
minimize the running time of the algorithm, we pro1. E.Ando, T.Nakata, M.Yamashita, Approximating thepose to approximate the inverse function of (F B (x))|P| .
Longest Path Length of a Stochastic DAG by a Normal
LetDistribution in Linear Time. Submitted for publication.
!!
22. E.Ando, M.Yamashita, T.Nakata, Y.Matsunaga, The Statisti1 x−µcal Longest Path Problem and Its Application to Delay AnalL(x; µ, σ 2 ) = exp − exp −+ ln ln 2.
2σysis of Logical Circuits. Proceedings of the International
Let µe and σe2 be, respectively, mean and variance ofThen we can prove that L(x; µ, σ 2 ) ≤ F (x) for x ≥ µwhere F (x) is the distribution function of N (µ, σ 2 ).
Since equation L(x; µ, σ 2 ) = a has two real solution
for 1/2 ≤ a < 1, we denote the larger solution byL−1 (a; µ, σ 2 ). Then we havepL−1 (a; µ, σ 2 ) = µ + σ −2 ln(− ln a) + 2 ln ln 2.
An upper bound on the inverse function of (F B (x))|P|
is given as

FB−1 (a1/|P| ) ≤ L−1 (a1/|P| ; µ, σ 2 )p= µmax +σmax 2(ln|P| − ln(−ln a))+2 ln ln2, (1)for 2−|P| ≤ a < 1. The approximation algorithm is tocalculatepA(a) = µmax +σmax 2(C −ln(−lna))+ 2 ln ln2,(2)Workshop on Timing Analysis (TAU2002), pp.134-139, 2002.
3. M.Berkelaar, Statistical delay calculation, a linear time
method. Proceedings of the International Workshop on Timing Analysis (TAU’97), pp.15-24, 1997.
4. C.E.Clark, The PERT model for the distribution of an activity
time. Operations Research 10, pp.405-406, 1962.
5. M.Hashimoto and H.Onodera, A performance optimization
method by gate sizing using statistical static timing analysis. IEICE Trans. Fundamentals, E83-A, 12, pp.2558-2568,
2000.
6. V.G.Kulkarni and V.G.Adlakha, Markov and MarkovRegenerative PERT Networks, Operations Research, Vol.34,
No.5, pp.769-781, 1986.
7. J.J.Martin, Distribution of the time through a directed,
acyclic network. Operations Research 13, pp.46-66, 1965.
8. D.G.Malcolm, J.H.Roseboom, C.E.Clark and W.Fazar, Application of a technique for research and development program evaluation. Operations Research 7, pp.646-669, 1959.
9. S.Tsukiyama, M.Tanaka and M.Fukui, An Estimation Algorithm of the Critical Path Delay for a Combinatorial Circuit.
IEICE Proceedings of 13th Workshop on Circuits and Systems, pp.131-135, 2000 (in Japanese).

8（第1分冊）