Let $G=(V,A)$ be a directed graph with distinguished vertex $s\in V$ and let $c:A\rightarrow{\mathbb N}$ denote arc capacities. For any $t\in V,t\not=s$ we are given two numbers: $C_{t},L_{t}$. Let $P_{s,t}=<v_{0}=s,v_{1},\ldots,v_{k}=t>$ be any $s-t$ path. Then, its total capacity is $C(P_{s,t})=\min_{i=0,\ldots,k-1}{c(v_{i},v_{i+1})}$ and its total length is $L(P_{s,t})=k$. Consider the decision problem: Are there $s-t$ paths such that $C(P_{s,t})\geq C_{t}$ and $L(P_{s,t})\leq L_{t}$, for any $t\in V,t\not=s$?
I need a proof that this problem is NP-complete.
Many Thanks!
