Computing the Stochastic Shortest Path Length Between Two Vertices with Exponentially Distributed Edge Lengths in Graphs with Small Treewidth

摘要

In this paper, we propose an algorithm for the stochastic shortest path problem between two vertices in an undirected graph G. In the stochastic shortest path problem, the edge lengths are random variables, so shortest path lengths are also random variables. Our goal is to compute the distribution function of the stochastic shortest path length in G. Unlike the shortest path problem with fixed edge lengths which can be solved in polynomial time, we show that computing the exact distribution function of the stochastic shortest path length is #P-complete even if the edge lengths can take only two discrete values. In contrast, we show how to efficiently compute the distribution function B_G{x) of the stochastic shortest path length of G with exponentially distributed edge lengths. Our algorithm outputs the description of B_G(x) as the sum of products of the polynomial of x and exponent of x. The running time of our algorithm is polynomial in the graph size, if the treewidth k of G are bounded by a constant.%本稿では，二点間の確率的な最短路問題に対する解法を提案する．確率的な最短路問題においては，与えとられた無向グラフC の各枝の長さが確率変数として与えられ，二点間の最短路長さもまた確率変数なる．本研究の目的はグラフC の最短路長さの分布関数を求めることである．まず本稿では，確定的な枝長さが与えられた場合の最短路問題が多項式時間で解けることとは異なり，確率的な最短路問題について，離散的な二値を取り得る枝長さを考えるとパスグラフにおいても＃P－完全である事をまず示す．次に，指数分布に従う枝長さを考えた場合にはこの確率的最短路問題をある程度効率的に解きうる事を示す．ここでの目的は最短路長さの分布関数B_G（x）を記述する数式を，x の多項式や指数関数の積の和として出力する事を行う．ここで，もし与えられたグラフGの木幅（treewidth）が定数k以下で各校長さが互いに独立で期待値1の指数分布に従うならば，提案手法はグラフの規模の多項式時間で完了する事を示す．