在具有起始节点和结束节点的有向图中，如何找到一个小的（不必是最小的）节点集，以便从起始节点到结束节点的每个可能路径都至少包含一个集的成员。请注意，图可能有循环。我知道这可能是np难的。
有没有从图中找到一个或几个这样的S的近似方法？
或者给定一个集合s，如何验证s是一个解？（图循环似乎使验证变得非常复杂。）
谢谢。
ps：这个问题类似于最小k-路径顶点覆盖问题。
最佳答案
对于（2），可以通过从图中删除所有有问题的节点，然后查看是否仍有s/t路径，轻松验证集合是否具有此属性。如果是这样，那么一定有一条路径不包含集合中的任何节点。如果不是，则每个路径必须至少包含集合中的一个节点。
不过，我不确定（1）。
希望这有帮助！
关于algorithm - 如何查找一小组顶点，以使图形中从起点到终点的所有路径都包含这些顶点中的至少一个，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10726625/