シンプルな削減（NP完全問題）

Question

私はbicriteria最短経路問題はNPの完全であることを証明するための手段を探しています。 、長さと重み付きグラフを考えると、私は全体の長さを有するT秒からグラフ内のパスが存在するかどうかを知る必要があること<= L及び重量<= W

私は私がNP完全問題を取ると、この1にそれを削減しなければならないことを知っています。私達は私達の処分でから選択するには、次のような問題があります。3-SAT、独立したセット、頂点カバー、ハミルトニアンサイクル、および3次元のマッチングを

実行可能とすることができる上の任意のアイデア？

感謝

Answer 1

は、Googleを試してみましたか？第三のヒットがあります：

のhttp：//www.jstage.jst .go.jp /物品/ ieejeiss / 128/3 / 128_416 / _article の

記事はペイパービューであるが、Googleのキャッシュ用品重要なビット先行ます：

"残念ながら、（bicriteriaの場合を含む）多目的場合はNP完全である（3）。

と基準点に

（3）M. GareyおよびD.ジョンソン：コンピュータ、および難治：NP完全性、ニューヨークの理論へのAガイド：フリーマン（1979）

この形式の質問のための標準的な基準である

だから... ...あなたはGareyとジョンソンで見たことがありますか？私がチェックするためにここにコピーを持っていないが、それは私のゴーに私はカンプをしたときだった。