2
$\begingroup$

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!

  • 0
    You can't use the Ford Fulkerson algorithm unless all capacities are integers since otherwise you are promised that the algorithm will stop.2012-08-28
  • 0
    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 it2012-08-28
  • 0
    @Belgi: I can assume that the capacities are integers. I add it to the answer. BTW Dinic and Dijkstra are only for integer capacities?2012-08-28
  • 0
    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 ?2012-08-28
  • 0
    I do not get the part: "where $f(e)$ is the maximum flow possible on the edge $e$ for it".2012-08-28
  • 0
    @belgi: no, we need to find the flow which maximize $f(e)$. It might not be the maximum flow of the network.2012-08-28
  • 0
    @utdiscant: see my last comment2012-08-28
  • 0
    @Jozef - this is not what I asked, I'm asking this: let as reduce ourselves to all the flows in which $f(e)$ is maximal - is every such flow good for you or do you want, among these flows, find one that maximizes the network (under the constraint that $f(e)$ is maximal) ?2012-08-28
  • 0
    @belgi find one that maximizes the network (under the constraint that f(e) is maximal).2012-08-28
  • 0
    FF and Dinic work adequately for non-integer capacities, but they are not necessarily guaranteed to terminate unless the quotient of every pair of capacities is a rational number. In practice this is never an issue, since computers represent non-integer numbers as fractions of the form $n\cdot2^{-i}$, the quotients of which are rational, and nobody cares about finding a maximal flow in a network with an edge whose capacity is precisely $\sqrt 2$.2012-08-28

1 Answers 1

1

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.

  • 0
    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 options2012-08-28
  • 0
    @Belgi, if no flow uses $e$ then the answer is zero, isn't it?2012-08-28
  • 0
    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)2012-08-28
  • 0
    @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.2012-08-29