SHORTEST WEIGHT-CONSTRAINED PATH

• INSTANCE: Graph $G=\left(V,E\right)$, length function $l:E \rightarrow N$, weight function $w : E \rightarrow N$, specified vertices $s,t \in V$, and integer W.

• SOLUTION: A simple path in G with total weight at most W, i.e., a sequence of distinct vertices $s=v_1,v_2,\ldots,v_m=t$ such that, for any $1 \leq i \leq m-1$, $(v_i ,v_{i+1}) \in E$ and $\sum_{i=1}^{m_1}w(v_i,v_{i+1}) \leq W$.

• MEASURE: The length of the path, i.e., $\sum_{i=1}^{m_1}l(v_i,v_{i+1})$.

  
  

• Good News: Admits an FPTAS [235] and [402].

• Garey and Johnson: ND30