证明 NP 完全性

Question

给定图的任意两个顶点之间的 m 条最短路径。确定我们是否可以选择 k 条最短路径，使其并集覆盖所有边。

我确信减少必须来自固定封面，但我不知道如何将它减少到这个问题。请帮助我

Answer 1

提示：请看下图。从 A 到 B 有很多不同的最短路径。你能用这样的图和一组路径对集合覆盖进行编码吗？ （好吧，你可能需要稍微修改一下图表，但这是一般的想法）。

   o     o     o     o     o     o     o     o     o     o     o     o     o
  / \   / \   / \   / \   / \   / \   / \   / \   / \   / \   / \   / \   / \
A     o     o     o     o     o     o     o     o     o     o     o     o     B
  \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /   \ /
   o     o     o     o     o     o     o     o     o     o     o     o     o

Answer 2

Update 不知道封面也是 NP 完全的。无需执行任何操作即可将原件放入确切的布景封面，因此我所做的 wlog 假设是没有必要的。但我也意识到我证明的基本思路是错误的：它表明当前问题是另一个问题的特例，这使得它更容易，而不是更难。完整和正确的答案由 mjqxxxx 在 https://math.stackexchange.com/q/2047262 给出。

让我们w.l.o.g。假设没有单个顶点属于超过 1 条路径（即路径对应于不同的顶点集）。

那么这个问题是一个精确覆盖问题（NP完全）扩展到找到所有确切的封面而不是任何一个（然后检查其中一个是否有确切的 k 元素——这种检查在一般情况下有点棘手）。 https://en.wikipedia.org/wiki/Exact_cover https://en.wikipedia.org/wiki/Set_cover_problem

集合X包含图的所有顶点，集合S包含对应于给定路径集的顶点集。