图：查找最小数量的节点，以便从a到b的每条路径都至少穿过其中一个

Question

我有一个无向图，它具有起点节点（比方说A）和终点节点（B）。如何找到最小数量的节点，以便从A到B的每条路径都至少穿过其中一个？附言节点A和B不计算在内。

Answer 1

此问题的一种解决方案是找到从A到B的每条路径，然后找到每条路径中包含的最小节点集。但这仅适用于小型图，因为这两个问题都是NP-Hard。因此，对于较小的图（可能多达约1000个节点），此解决方案可能会在可接受的时间内工作，但对于较大的图，可能会花费太长时间。

要查找从A到B的所有可能路径，可以检查this answer或implementation here。

找到所有路径后，可以将路径作为sets S处理（其中S是一组集合），然后尝试查找包含以下内容的新集合T： S中每个集合的至少一个元素。如this answer中所述，此问题称为Hitting-Set-Problem，它具有一些已知的算法来计算此问题的解决方案，例如this approximation algorithm（但我没有找到该算法的实现）。

Answer 2

使用最大流量可以有效解决此问题。

给定图G'=（V，E），创建一个新图G'=（V'，E'，其中V'= V×{in，out}由顶点v _in和v 且E'= E _∞∪E ₁其中E _∞ = {v _out→w _in | （v→w）＆in; E}在E中的每个边都有一个弧，并且E ₁ = {（v _in→v _out）| v＆in; V}有一个V中每个顶点的圆弧。E_∞中每个圆弧的容量是无限的，E ₁中每个圆弧的容量是1。找到从A _out到B _in和相应的最小切割C。对于E ₁中与C交叉的每个弧，应从G中删除相应的顶点。