Modification to Maximum Flow Algorithm

Question

I've tried to solve a question about the maximum-flow problem. I have one source and two sinks. I need to find a maximum flow in this network. This part is general max-flow. However, both targets have to get same amount of flow in this special version of the max-flow problem.

Is there anyone who can help me what should I do to do that?

Calandra

What is the reason of -1 ? – Calandra

Are you talking fluid analysis or computer network messages? – Obrian

I would start with something along the lines of the same way you'd do general max flow, except at each step, find two augmenting paths, one from the source to each target. Then add enough flow to both paths such that both targets still get the same amount of flow (this is complicated a bit by non-edge disjoint graphs). I'm not sure that doing this will actually result in the max possible for both targets. – Sext

How is the question "unclear"? It's very obvious what is asked, IMHO. Actually in interesting problem. – Neile

Answer 1

Let s be your source vertex and t1 and t2 the two sinks.

You can use the following algorithm:

1. Use regular max-flow with two sinks, for example by connecting t1 and t2 to a super-sink via edges with infinite capacities. You now have the solution with maximum excess(t1) + excess(t2), but it might be imbalanced.

2. If excess(t1) == excess(t2), you are done. Otherwise, w.l.o.g. let excess(t1) > excess(t2)

3. Run another round of max-flow with source t1 and sink t2 in the residual network of step 1. Restrict the flow outgoing from t1 to c = floor((excess(t1) - excess(t2)) / 2), for example by introducing a super-source S connected to t1 via an edge with the given capacity c. Now, excess(t2) is the maximum flow you can send to both sinks.

4. If you need to reconstruct the flow values for each edge, do another round of max-flow to transport the excess(t1) - excess(t2) leftover units of flow back to the source.

The complexity is that of your max-flow algorithm.

If you already know how to solve max-flow with lower-bound capacities, you can also binary search the solution, resulting in complexity O(log W * f) where W is the solution value and f is the max-flow complexity.

Neile

I'm sorry its not clear how adding a super source to t1 will transfer the flow units to t2. As far as I understand t1 will still remain a sink and transfer of flow 'from' t1 to any other node will be impossible. Sorry again if I mis-understand. – Thorndike

@AbhishekBansal treat t1 as a normal node and t2 as sink and proceed to do max-flow from new source to t2 – Cinda

to author: can you explain more explicitly about step 4? – Cinda

@KudayarPirimbaev t1 has all its edges as incoming edges (since it is a sink). How can it be considered a normal node? – Thorndike

@AbhishekBansal i think it is assumed that graph is bidirectional, in your case, i guess, you need to reverse directions of all edges to t1 except the one from new source, try like that, i'm not sure – Cinda

@AbhishekBansal: "t1 has all its edges as incoming edges (since it is a sink). How can it be considered a normal node". Doesn't matter. You just add an additional incoming edge that has capacity floor((excess(t1) - excess(t2)) / 2) and add it to a newly introduced source S. You can also think about it as setting supply(t1) = floor((excess(t1) - excess(t2)) / 2) and demand(t2) = ∞. The super-source is just a way to solve that. – Neile

@KudayarPirimbaev: Let's say in the initial max-flow, t1 receives 6 units of flow and t1 receives 2. We now try to transfer 2 unit of flow from t1 to t2 for balancing. Now it might happen that this doesn't work, we just achieve to send 1 unit of flow from t1 to t2, so we end up with excess(t1) = 5 and excess(t2) = 3. The solution here is that both nodes receive 3 units of flow (the minimum of the two), so we need to send 2 units of flow from t1 back to the original source in the residual network (another max-flow problem). – Neile

@KudayarPirimbaev: And no, the graph is not assumed to be bidirectional. The algorithm would still work though. – Neile

@AbhishekBansal: Sorry, I think I now understand better where you had a problem understanding the algorithm: "As far as I understand t1 will still remain a sink and transfer of flow 'from' t1 to any other node will be impossible." We are working on the residual network after step 1, so if excess(t1) != 0, then it will in fact have some outgoing residual edges! – Neile

@NiklasB. so to balance to 3 (in this example), we should apply max-flow where source is t1 and sink is s? – Cinda

@KudayarPirimbaev: Yep. In the residual network after step 3, that is. Of course we only need to do this if we want the complete flow function, since we already know the value of the solution is 3. – Neile

@NiklasB. I tried your algorithm using Edmonds-Karp. It updates flows correctly in the first step, but then it fails to update properly when I do it for supersource and sink t2 as well as when applying it in step 4. I think I implemented the Edmonds-Karp algorithm correctly, what can be my mistake in your opinion? – Cinda

@Kudayar: Do you always use the residual network from the last step? – Neile

@NiklasB. Yes, only Edmonds-Karp itself changes flow matrix – Cinda

@Kudayar: What do you mean by "fails to update properly"? I mean it should always respect the flow balance and flow conservation constraints. If it does and there exists a residual path from t1 to t2 in step 3, it should find it. It should never enter an inconsistent state. – Neile

let us continue this discussion in chat – Neile

@NiklasB. fixed it, was improperly using breadth-first, thanks for help – Cinda

@NiklasB. Thank you, I understand now. I had forgotten that we are working on the residual graph, not the original one. – Thorndike