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
    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
    @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