最短重み制約付き経路問題の NP 完全性を証明しようとしています。私は複数の論文を読みましたが、神の愛のために、これをパーティションの問題に還元する方法を理解できません。
重み w と長さ l の各エッジについて質問が与えられ、無向グラフの場合、パスの重みの合計 < W およびパスの長さの合計 < L となるようなパスを見つける問題が示されます。ここで、L W は問題で与えられた定数です。
私は、問題が NP 完全であり、証明する方法や削減を提供していないと述べている Garey と Johnson を見ました。