Computing a Most Probable Delay Constrained Path: NP-Hardness and Approximation Schemes

Delay constrained path selection is concerned with finding a source-to-destination path so that the delay of the path is within a given delay bound. When the network is modeled by a directed graph where the delay of a link is a random variable with a known mean and a known variance, the problem becomes that of computing a most probable delay constrained path. In this paper, the authors present a comprehensive theoretical study of this problem. First, they prove that the problem is NP-hard. Next, for the case where there exists a source-to-destination path with a delay mean no more than the given delay bound, they present a fully polynomial time approximation scheme.