1
$\begingroup$

When solving a multi source/sink max flow problem, the classic reduction to the single source/sink problem is to add a new source and sink node with infinite capacities that connect to/from the existing source/sink nodes.

I was curious about an alternate reduction. It is kind of silly buy I just wanted to sanity check it.

Is it possible to group all the source nodes into one big source node, with all the outgoing edges of the original source nodes now added to the mega source node. We can collapse repeated edges by adding up their capacities. A similar thing can be done for sink nodes.

Let's say I have a solution to the mega source/sink problem. You would have to keep track of which edges in the mega source/sink node correspond to which edges in the original sources/sinks, and choose the same corresponding flow for the original source nodes' edges. For two edges that you collapsed in the mega node by summing their capacities, you can just distribute the flow arbitrarily amongst the original source nodes (maintaining the capacity constraints).

Does this approach fail catastrophically or sound reasonable?

$\endgroup$
4
  • $\begingroup$ You haven't described your approach completely. How do you convert a solution for the new instance to one for the original instance? Try proving that your approach works. If you succeed, then it works. If not, try finding a counterexample. If you succeed, then your approach doesn't work. $\endgroup$ Apr 19, 2021 at 6:16
  • $\begingroup$ @YuvalFilmus I've clarified a little. I suppose the proof idea so far is that the two problems are isomorphic in that any flow in the mega graph can be represented 1:1 as a flow in the original graph and vice-versa. The only complication is when you collapse edges in the mega graph by summing the individual edges of original sources that have the same destination. But in this case, you can just distribute the flow to the original source nodes however you want. $\endgroup$
    – gowrath
    Apr 19, 2021 at 7:43
  • $\begingroup$ I encourage you to try to work it out on your own, and come back here only if you are stuck. It is within your capabilities. $\endgroup$ Apr 19, 2021 at 7:45
  • $\begingroup$ @YuvalFilmus Thank you, I appreciate the encouragement. I have thought of it already, which is why I'm posting a question here. A formal proof would be to say that both graphs have the same max flow value because they have the same min-cuts. All you then have to prove is that the flow on the super graph is a valid flow on the original graph (translated according to the description), and has the same flow value. I have already described why I think this is true. If you think it is incorrect or needs could be more rigorous, please feel free to say something more specific. $\endgroup$
    – gowrath
    Apr 19, 2021 at 8:01

1 Answer 1

1
$\begingroup$

That would actually work as well, but it is more cumbersome than just adding a new source and sink.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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