shortest-path - 简单归约（NP 完备性）

Question

我正在寻找一种方法来证明 bicriteria 最短路径问题是 np 完备的。也就是说，给定一个具有长度和权重的图，我需要知道图中是否存在从 s 到 t 的总长度 <= L 且重量 <= W 的路径。

我知道我必须解决一个 NP 完全问题并将其简化为这个问题。我们有以下问题可供选择：3-SAT、独立集、顶点覆盖、汉密尔顿循环和 3 维匹配。

任何可能可行的想法？

谢谢

Answer 1

你试过谷歌吗？第三次打击是：

http://www.jstage.jst.go.jp/article/ieejeiss/128/3/128_416/_article

这篇文章是按次付费的，但谷歌缓存预先提供了重要的一点：

“不幸的是，多目标案例（包括 bicriteria 案例）是 NP 完全的（3）。

参考指向：

(3) M. Garey 和 D. Johnson：计算机和难处理性：NP 完备性理论指南，纽约：弗里曼 (1979)

这是此表格问题的标准参考。

所以……你看过加里和约翰逊吗？我这里没有要检查的副本，但这是我做伴奏时的首选。