Dear David, David Doria wrote:
2) Is it possible to tell the max flow algorithm to use multiple sources/sinks? You have to add one global source and sink node and connect everything else to it to achieve this effect.
2) I guess my phrasing wasn't very clear. Basically what it would be nice to do is specify a list of nodes that are definitely on one side of the cut, and a second list of nodes which are definitely on the other side of the cut. The cut would then be constrained so that these two sets indeed lie on different sides of the cuts. VERY simple examples (a graph with < 10 nodes) should be provided to demonstrate (1) and (2).
Actually, now that I thought about it more carefully, what I said before is the correct way to exactly solve your problem. Consider a weighted digraph and two non-empty disjoint subsets S, T of the vertex set. Then, you can solve for the minimum S-T min-cut by adding two new vertices u, v, and connect u->s for all s in S, and t->v for all t in T. All these new edges receive a weight of positive infinity, thus can never be saturated in a max-flow solution and never be cut in a min-cut. Then, solving for the u-t min-cut will also solve for the S-T min-cut. Sebastian