algorithm - 如何找到一小组顶点，使得图中从起始节点到结束节点的所有路径都至少包含这些顶点中的一个

Question

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

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

2. 或者给定一个集合 S，我如何验证 S 是一个解？ (图循环似乎使验证变得非常复杂。)

谢谢。

PS:本题类似于Minimum k-path vertex cover problem。

Answer 1

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

不过，我不确定 (1)。

希望这对您有所帮助!