如何找到分离一些节点对的整体最小切割
问题描述：
如我们所知，现在有高效的算法来找到有向图中的总体最小切割，例如，郝和奥林（1994）。如何找到分离一些节点对的整体最小切割
现在我的问题是找到一个整体最小切割只是分离一些给定的节点对，而不是所有的节点对。例如，我在每个弧上有一个8节点的有向图，并且想要找到最小切割分离8和1,6和3,7和1.
非常感谢。
答
你想解决最小多重分割问题，这是NP-Hard，但也在文献中进行了广泛的研究。 例如http://scholar.google.be/scholar?q=minimum+multicut+directed+graph&btnG=&lr=
我想你不明白我的问题。正如我所提到的那样，现在有高效的算法来查找分离所有节点对的整体最小切割。在这里，我想要一个很好的算法来找到仅仅分离一些节点对的总体最小切割。 – shaon
我想我确实理解你的答案:)。你想*找到总体最小切割只是分离一些节点对。*这就是所谓的*多*剪切。这个问题是一个开放的研究问题，据我所知，没有“好”的算法，因为这个问题太难了。大多数算法都是随机的，或者只处理图表的某个子类，例如http://arxiv.org/abs/1206.3999 所以你应该看看哪种算法最适合你的需求。 – Dave
非常感谢。我想我没有清楚地解释我的问题。我的问题不同于最小多重分割问题，即找到一组最小权重边，这些边的去除将每对给定源和汇集分隔开。但我的问题是要确定每个节点对的所有切割的最小值。例如，我有一个4节点的有向图和节点对{1,4}，{2,4}和{1,3}。然后，我想要找到最小的一个，其中最小的一个是分割1和4，最小的是分割2和4，最小的是分割1和3. – shaon