Computing a most probable delay constrained path: NP-hardness and approximation schemes

Ying Xiao, Krishnaiya Thulasiraman, Xi Fang, Dejun Yang, Guoliang Xue

Research output: Contribution to journalArticlepeer-review

29 Scopus citations


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, we present a comprehensive theoretical study of this problem. First, we 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, we present a fully polynomial time approximation scheme. In other words, for any given constant ε such that 0 < ε < 1, our algorithm computes a path whose probability of satisfying the delay constraint is at least (1-\epsilon ) times the probability that the optimal path satisfies the delay constraint, with a time complexity bounded by a polynomial in the number of network nodes and 1/ε. Finally, for the case where any source-to- destination path has a delay mean larger than the given delay bound, we present a simple approximation algorithm with an approximation ratio bounded by the square root of the hop count of the optimal path.

Original languageEnglish (US)
Article number5740849
Pages (from-to)738-744
Number of pages7
JournalIEEE Transactions on Computers
Issue number5
StatePublished - 2012


  • Delay constrained path selection
  • approximation schemes
  • computational complexity

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Computing a most probable delay constrained path: NP-hardness and approximation schemes'. Together they form a unique fingerprint.

Cite this