在具有起始节点和结束节点的有向图中，如何找到节点的小(不必是最小的(集合S，以便从起始节点到结束节点的每个可能路径都包含至少一个集合S的成员。我知道这可能是NP困难的。
-
有没有一种近似的方法可以从图中找到一个或多个这样的 S？
-
或者给定一个集合 S，我如何验证 S 是一个解决方案？(图形循环似乎使验证非常复杂。
谢谢。
PS：这个问题类似于最小k路径顶点覆盖问题。
对于 (2(，您可以通过从图形中删除所有有问题的节点，然后查看是否仍有 s/t 路径来轻松验证集合是否具有此属性。 如果是这样，那么一定有一些路径不包含集合中的任何节点。 如果不是，则每个路径必须至少包含一个集合中的节点。
不过，我不确定(1(。
希望这有帮助！