Given a flow network $G=(V,E)$, source $s$ , sink $t$ and capacity function $c:E \to \mathbb{R}^+ \cup \{0\}$ ; as well an edge $e=(u,v) \in E$. I need to find an efficient algorithm which finds among all possible flows between $s$ and $t$ , a flow $f$ where $f(e)$ is the maximum flow possible on the edge $e$ for it.

I want to use Ford Fulkerson algorithm but instead of using BFSs one after the other and increase the flow, first use all the paths through $e$, and then after we don't find any, go on with any path available to $t$ from $s$, or something in this direction..

Edit: You can assume that the capacities are integers.

Thanks a lot!

  • $\begingroup$ You can't use the Ford Fulkerson algorithm unless all capacities are integers since otherwise you are promised that the algorithm will stop. $\endgroup$ – Belgi Aug 28 '12 at 10:42
  • $\begingroup$ By the way, I would first try to make a reduction to an existing algorithm and only upon failing I would start to consider changing it $\endgroup$ – Belgi Aug 28 '12 at 10:50
  • $\begingroup$ @Belgi: I can assume that the capacities are integers. I add it to the answer. BTW Dinic and Dijkstra are only for integer capacities? $\endgroup$ – Jozef Aug 28 '12 at 11:03
  • $\begingroup$ I don't remember, you can look this up easily in Google though. Among all flows where $f(e)$ is maximal, are we required to find one that maximizes the flow of the network ? $\endgroup$ – Belgi Aug 28 '12 at 11:33
  • $\begingroup$ I do not get the part: "where $f(e)$ is the maximum flow possible on the edge $e$ for it". $\endgroup$ – utdiscant Aug 28 '12 at 13:14

Try this: let $e$ join $v$ to $w$, delete every edge that is neither in a path from source to $v$ nor in a path from $w$ to sink, and find a maximal flow in what's left of the network.

EDIT: Here's another way to achieve this. Reviewing the notation: the source is $s$, the sink is $t$, the edge $e$ joins $u$ to $v$. Make believe the sink is $u$, and find a maximal flow in the network; let its value be $a$. Now make believe the source is $v$, and the sink is $t$, and find a maximal flow; let its value be $b$. Then the maximal flow achievable in $e$ is the smallest of the numbers $a$, $b$, and the capacity of $e$. Moreover, you can easily adjust the flows you have found to a flow with that maximal amount going through $e$ and with the rest of the flow maximal subject to that restriction.

  • $\begingroup$ You are not guaranteed that you can even send some flow from $s$ to $t$ since if no flow uses $e$ you deleted the other options $\endgroup$ – Belgi Aug 28 '12 at 13:55
  • $\begingroup$ @Belgi, if no flow uses $e$ then the answer is zero, isn't it? $\endgroup$ – Gerry Myerson Aug 28 '12 at 22:38
  • $\begingroup$ Technicly the answer is any flow (the answer is not a number...). and I just wanted to point to the first thing that came to mind...I still think that the solution is incorrect (thats my intuition) $\endgroup$ – Belgi Aug 28 '12 at 22:43
  • $\begingroup$ @Belgi, different flows have different values for $f(e)$, so I don't see how the answer can be "any flow". And Mathematics doesn't necessarily accord with your intuition. My proposed solution may be incorrect, but I'd like to see an example where it gives the wrong answer. $\endgroup$ – Gerry Myerson Aug 29 '12 at 1:41

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.