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).
$s$ - source
$t$ - sink
$f(e)$ - flow at edge $e$
$c(e)$ - capacity at edge $e$
$v(f)$ - value of flow
- 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.
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.