证明最优路径覆盖的NP完备性
Proving NP completeness of optimal path cover
这个paper解决了块图或二部置换图的最优路径覆盖问题。在介绍的第三行写到optimal path cover problem is NP-Complete 并且参考了"Computer and intractability: a guide to the theory of NP-completeness by David S. Johnson, Michael R. Garey"。但我在书中找不到它的证据。如果有人知道如何证明此问题的 NP 完全性，请分享您的解决方案。
Optimal path cover problem:
Given a graph G, find a minimum number of
vertex disjoint paths which together cover all the vertices of the
graph.
考虑明显的决策变体（即给定k，是否有k条路径的覆盖）
OPC(k=1) 检测哈密顿路径，很明显它是 NP 难的。
它也在 NP 中，因为给定路径，检查它们是否不相交和覆盖很容易。
这个paper解决了块图或二部置换图的最优路径覆盖问题。在介绍的第三行写到optimal path cover problem is NP-Complete 并且参考了"Computer and intractability: a guide to the theory of NP-completeness by David S. Johnson, Michael R. Garey"。但我在书中找不到它的证据。如果有人知道如何证明此问题的 NP 完全性，请分享您的解决方案。
Optimal path cover problem:
Given a graph G, find a minimum number of vertex disjoint paths which together cover all the vertices of the graph.
考虑明显的决策变体（即给定k，是否有k条路径的覆盖）
OPC(k=1) 检测哈密顿路径，很明显它是 NP 难的。
它也在 NP 中，因为给定路径，检查它们是否不相交和覆盖很容易。