most recent 30 from http://mathoverflow.net 2013-06-19T22:53:22Z http://mathoverflow.net/feeds/question/29404 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29404/network-flow-gadget Michael Biro 2010-06-24T16:29:02Z 2010-06-25T00:37:52Z

<p>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?</p> <p>If m = 1, we can just connect the source to the destinations and use the integral flow theorem, but what about m > 1?</p>

http://mathoverflow.net/questions/29404/network-flow-gadget/29452#29452 David Eppstein 2010-06-25T00:37:52Z 2010-06-25T00:37:52Z

<p>No, there is no such gadget.</p> <p>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.</p> <p>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.</p> <p>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.</p>