这paper解决 block 图或二部置换图的最优路径覆盖问题。在其介绍的第三行中写道，最佳路径覆盖问题是 NP 完全问题，并引用了“计算机和难处理性:David S. Johnson，Michael R. Garey 的 NP 完整性理论指南”。但我在书中找不到它的证据。如果有人知道如何证明此问题的 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 中，因为给定路径，检查它们是否不相交和覆盖很容易。
关于algorithm - 证明最优路径覆盖的NP完备性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40888929/