2
$\begingroup$

Flow networks are often constructed when one is interested in measuring how resilient a graph is. The idea goes as follows: two vertices are designated as source $(s)$ and sink $(t)$ respectively, to each edge $e$ of the graph a capacity $c_e$ is assigned (which can be defined as a function vertex properties of the endpoints of an edge), and in analogy to flow of water through pipes for example, a net flow is assumed to take place from the source towards the sink. That is the net flow out of the source, is equal to the net flow entering the sink: $$ \sum_{u\in O(s)} f(s,u)-\sum_{u\in I(s)}f(u,s)=\sum_{u\in I(t)} f(u,t)-\sum_{u\in O(t)}f(t,u) $$ where $O(s)$ denotes the set of vertices, that $s$ is incident on, and $I(s)$ denotes the set of vertices that are incident to $s.$ Now often, one is interested in computing the maximum possible flow in the graph, which leads to using Menger's theorem, which relates maximum number of distinct paths (between $s$ and $t$) to the minimal cut-set, or in a general setting, it relates the maximum flow to minimum cut capacity (summing the capacities of the minimum cut, that disconnects source from sink).

There are many algorithms that allow computing the maximum flow rather efficiently, for a given digraph. But my questions are (sadly) rather basic, but are solely related to computing maximum flow:

  • Assuming the capacities of all the edges are known, why the computation of maximum flow does not(?) depend on the net outward flow from the source, and instead it is only a function of the capacities? or am I wrong?
  • How are then the individual flows $f$, through each edge $e$ (where $f_e\le c_e $), calculated when we are estimating the maximum flow? Do we set all flows equal to respective capacities (i.e. $f_e=c_e$)? Or is the individual flow, a function of the minimum capacity ($\text{min}(c_e)$ for all edges $e$) of the graph?
  • Of course it is possible that I'm completely wrong here, in which case, the question becomes: how is the flow decided for each edge (knowing at least that $0\le f_e \le c_e$ for all edges), when we are interested in estimating the maximum flow through the graph?
$\endgroup$
3
$\begingroup$

I think all your questions are answered by examining the actual algorithm to compute the max flow.

With regards to your Q1: in the max flow problem your input is a graph and capacities on edges, your output is the max flow. Thus, max flow is a function of the graph and capacities.

The basic algorithm for computing max flow is as follows. Your capacities are $c: E \rightarrow \mathbb{R}$. We shall incrementally compute the flow $f: E \rightarrow \mathbb{R}$. Let $f^i$ be the flow in iteration $i$. To begin with set $f^0 = 0$. In iteration $i$ construct the residual capacities $c^i(e) = c(e) - f^i(e)$ - this is how much capacity is left on edge $e$ given that we are already sending $f^i(e)$ flow through it. Find an augmenting path from $s$ to $t$, i.e., any path $p$ from $s$ to $t$ such that all edges on that path have positive residual capacity. How much flow can you push on this path? Clearly it's the minimum capacity along an edge of that path $f_{add} = \min_{e \in p} c^i(e)$. Update your flow by pushing $f_{add}$ flow along path $p$. This process naturally stops when your residual graph does not have an augmenting path from $s$ to $t$. It's a fact that at that point the flow you constructed is, indeed, the maximum flow. This fact requires a proof. This is a meta-algorithm (called Ford-Fulkerson), because I have not specified how to choose augmenting paths. Certain choices are better than others. Using BFS (in which case, this max flow algorithm has a name of Edmonds-Karp) to choose the augmenting path results in a polynomial time algorithm, but it again requires proof.

$\endgroup$
  • $\begingroup$ Many thanks for your reply. This is exactly the type of answer I was hoping for. Im going to read up more on the points you mention before asking further questions. Just a question that pops to mind immediately is: lets take a network with 4 paths only between s and t (just as illustrative example), these paths may share vertices or edges (thus not distinct), then is it correct to say that finding the maximum flow boils down to finding the path that maximises the minimum capacity, among the 4 possible paths, is this about right? $\endgroup$ – user929304 May 17 '16 at 21:04
  • $\begingroup$ Suppose that you find a path that maximizes minimum capacity among the 4 possible paths. When you push the min capacity flow through it the path would disappear from the residual graph in the next iteration; however, other paths might have survived, so you will repeat the process with the surviving paths. In general, you want selection of a path to be (a) efficient, and (b) terminate after a polynomial number of iterations. Finding a path that maximizes the minimum capacity is an overkill, since a BFS path already satisfies (a) and (b). $\endgroup$ – Denis Pankratov May 17 '16 at 21:36
  • $\begingroup$ I found the answer to most of my questions by reading up on the Ford-Fulkerson method e.g. here cse.psu.edu/~sxr48/cse565/lecture-notes/07demo-maxflow.pdf by going through the evolution of the residual network and the network itself as we try to increase the flow and keep looking for new augmented paths. Thanks again for your reply. Such fascinating field, would there be any specific book you'd recommend on network flows? (more on the application side, rather than proofs) $\endgroup$ – user929304 May 20 '16 at 15:28
3
$\begingroup$

why the computation of maximum flow does not(?) depend on the net outward flow from the source, and instead it is only a function of the capacities?

This is a bit like asking, "Why does the top speed of my car not depend on the speed I'm doing at the moment, and instead it is only a function of the power of its engine?"

The amount of water leaving the source is a property of a specific flow: different flows will have different amounts of water leaving the source. The maximum possible flow depends on the capacities of the edges in the graph, but it doesn't depend on whatever other flow you happen to be thinking about at the moment.

How are then the individual flows $f$, through each edge $e$ (where $f_e\leq c_e$), calculated when we are estimating the maximum flow?

By using one of the algorithms that does that. I suggest you look at a description of one of these algorithms.

$\endgroup$
  • 2
    $\begingroup$ Your first paragraph felt like an awakening slap in the face, very useful!!! I was really going about it all wrong there. $\endgroup$ – user929304 May 17 '16 at 20:57

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.