Consider a directed tree $G$ with a root node $s$. Let $s$ be the source node of $G$ and its leaves the sink nodes (call these leaves $t$). (And of course edges have their respective capacities like any network flow problem).
Notations used
$s$ – source
$t$ – sink
$f(e)$ – flow at edge $e$
$c(e)$ – capacity at edge $e$
$v(f)$ – value of flow
Greedy algorithm
- Start with $f(e) = 0$ for all edges in $G$.
- Find an $s-t$ path where for each edge $e$, $f(e) < c(e)$, and augment flow
along this path until one of the edges in this path reaches capacity.
Redo this step for another $s-t$ path where $f(e) < c(e)$ for all edges
in the path. Redo until there are no more paths left to augment flow.
Prove that this greedy algorithm successfully computes the max flow of $G$, or show a counterexample.
Attempt
I originally believed this problem to be false as I've encountered a few examples of greedy algorithm being used to demonstrate incorrectness. But after thinking it over I realized I missed a crucial detail that differentiates this from any other graph greedy max flow attempts as this is a tree. I believe this very fact of it being a tree – no cycles! – makes the difference to allow this algorithm to work.
The reason why this works seems fairly obvious at first, yet I have a hard time convincing myself so.
By picking an arbitrary path from the root node to a leaf and augmenting flow, while this may effect the amount of flow that can be sent along a similar $s-t$ path that shares some edges from upper level, it should not alter the overall flow value sent to the sinks as whatever flow entering must reach the sink (leaves) (This detail is more apparently if I look at the tree using its recursive definition using subtree nodes). Since every node has only one in degree it is only receiving flow from one source only so it can simply distribute it to its children (if any) freely without having to concentrate hard to maximize flow in general graphs. We can simply repeat this process until the edges – either at top level at source or anywhere else in path – are full at capacity.
I think I have the basics to start the proof but I'm having problems formalizing it (not sure how to apply your usual greedy algo proof here since there technically is no "conflict" per se…). But then again, I could be wrong and be missing a counter example.
Any input would be appreciated. Thanks.
Best Answer
First of all, the algorithm terminates because at least one edge is saturated in each step and there is a finite number of edges. Now let $f$ be the resulting flow, and assume $f'$ is some greater flow through the tree. For $f'$ to be a greater flow than $f$, we must have $f'(e)\gt f(e)$ for at least one edge $e$ leading away from the source. Now apply the same argument to the edges leading away from the final vertex of $e$, and continue this process until you've reached a leaf. The result is a path from $s$ to a leaf in which every edge has greater flow in $f'$ than in $f$. So this is a path along which the algorithm could have augmented $f$. The contradiction shows that there is no such flow $f'$, and so $f$ is maximal.