0

As we know, now there is efficient algorithms to find the overall min-cut in a directed graph, e.g. Hao and Orlin (1994).

Now my problem is to find an overall min-cut just separating some given node pairs, not all the node pairs. For example, I have an 8-node digraph with capacities on each arc and want to find the min-cut separating 8 and 1, 6 and 3, 7 and 1.

Thanks a lot.

1 Answer 1

0

You want to solve the minimum multicut problem, which is NP-Hard but also extensively studied in literature. E.g. http://scholar.google.be/scholar?q=minimum+multicut+directed+graph&btnG=&lr=

6
  • I think you did not understand my question. As I mentioned, now there are efficient algorithms for finding overall min cut separating all node pairs. Here, I want a good algorithm to find overall min cut just separating some node pairs.
    – shaon
    Dec 20, 2012 at 23:59
  • I think I did understand your answer :). You want to find overall min cut just separating some node pairs. And this is called a multicut. This problem is an open research question, and as far as I know, there is no "good" algorithm because the problem is so hard. Most algorithms are stochastic or tackle only a certain subclass of graphs, eg arxiv.org/abs/1206.3999 So you should look which algorithm best suits your needs..
    – Dave
    Dec 21, 2012 at 13:16
  • Thanks a lot. I think I did not explain my question clearly. My problem is different from the minimum multicut problem, which is to find a minimum weight set of edges whose removal separates each pair of given source and sink. But my problem is to determine the minimum from all cuts separating each node pair.For example, I have a 4-node digraph and node pairs {1,4},{2,4} and {1,3}. Then I want to find the minimum one among min-cut separating 1 and 4, min-cut separating 2 and 4, and min-cut separating 1 and 3.
    – shaon
    Jan 3, 2013 at 2:47
  • In that case, the easiest solution is to calculate the min-cut for each pair, and pick the cheapest one. I do not think much speed-up can be expected by solving the problem in one combined step.
    – Dave
    Jan 3, 2013 at 15:16
  • Yes, this is a difficutly job. I am still trying to modify the algorithm implementation of Hao and Orlin (1994) for my purpose. The current difficutly is how to exclude those cuts separating some not-considered node pairs.
    – shaon
    Jan 4, 2013 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.