2

在具有起始节点和结束节点的有向图中，如何找到一个小的（不一定是最小的）节点集 S 使得从起始节点到结束节点的每条可能路径都包含至少一个设置 S。请注意，图形可能有循环。我知道这可能是 NP 难的。

  1. 有没有一种近似的方法可以从图中找到一个或几个这样的 S？

  2. 或者给定一个集合 S，我如何验证 S 是一个解决方案？（图循环似乎使验证非常复杂。）

谢谢。

PS：这个问题类似于Minimum k-path vertex cover problem。

4

1 回答 1

1

对于 (2)，您可以通过从图中删除所有有问题的节点然后查看是否仍然存在 s/t 路径来轻松验证集合是否具有此属性。如果是这样，那么一定有一些路径不包含您的集合中的任何节点。如果不是，则每条路径都必须包含该集合中的至少一个节点。

不过，我不确定（1）。

希望这可以帮助！

于 2012-05-23T20:08:08.793 回答