简单还原（NP完整性）

Question

我在寻找一种方法来证明bicriteria最短路径问题是NP完全。 也就是说，给定与长度和重量的曲线图，我需要知道如果存在在从s曲线图中的路径与总长度<= L和重量为t <= W

我知道我必须采取NP完全问题，它减少到这一个。我们有我们所掌握以下问题可供选择：3-SAT，独立设置的，顶点覆盖，哈密顿圈和3维匹配

任何想法上其可以是可行的？

感谢

Answer 1

你有没有尝试谷歌？第三命中是：

HTTP：//www.jstage.jst .go.jp /条/ ieejeiss / 128/3 / 128_416 / _Article

这篇文章是付费观看，但谷歌的缓存提供前期最重要的一点：

“不幸的是，多目标的情况下（包括bicriteria情况下）是一个NP完全（3）。

和基准点为：

（3）M. Garey和D.约翰逊：计算机和顽固性：指南NP-完整性，纽约的理论：弗里曼（1979）

这是这种形式的问题的标准参考。

所以...你看着Garey和Johnson？我没有副本这里来检查，但它是我去到的时候我做了谱曲。