0

本文解决了块图或二部置换图的最优路径覆盖问题。在其介绍的第三行中，写到最优路径覆盖问题是 NP-Complete 并参考了“Computer and intractability: a guide to the theory of the theory of NP-completeness by David S. Johnson, Michael R. Garey”。但我在书中找不到它的证据。如果有人知道如何证明这个问题的 NP 完备性，那么请分享您的解决方案。

最优路径覆盖问题：
给定一个图 G，找到最小数量的顶点不相交路径，它们一起覆盖图的所有顶点。

4

1 回答 1

2

考虑到明显的决策变量（即给定 k，是否有 k 个路径的覆盖）

OPC(k=1) 检测哈密顿路径，很明显它是 NP 难的。

它也在 NP 中，因为给定路径，检查它们是否不相交和覆盖很容易。

于 2016-11-30T13:02:48.293 回答