Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given m units of flow from a source node, and several possible destinations, is there a network flow gadget to force the flow to use only one destination? That is, send all m units to one (unspecified) destination and 0 to all the others?

If m = 1, we can just connect the source to the destinations and use the integral flow theorem, but what about m > 1?

share|improve this question
add comment

1 Answer 1

up vote 3 down vote accepted

No, there is no such gadget.

Suppose to the contrary that you want to allow flow from vertex x to either vertex y or vertex z, but that you want it to remain unsplit. If there exist two flows F1 and F2, both with m units into vertex x but with those units all going to vertex y in flow F1 and all going to vertex z in flow F2, then for any 0 ≤ p ≤ m there exists a flow F3 with p units from x to y and m – p units from x to z: simply let F3 = (p/m)F1 + ((m–p)/m)F2. It's easy to verify that, if F1 and F2 obey the flow constraints at each vertex and edge, then so does F3.

In order to force the flow to be unsplit, you can't remain within the formulation of a maximum flow; you'd have to extend the problem to include additional side constraints, and by doing so most likely make it NP-hard.

There's one possible exception: if every node of the graph has the same value m and you want to quantize flow in units of m rather than in integers. Then you can just divide everything by m and use an integer flow.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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