Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
I agree with you that the greedy algorithm probably works, and for the reason you say. The first thing that comes to my mind is to try induction on the size of the tree, perhaps on the depth of the tree. –  MJD Mar 27 '12 at 13:28
2  
In a tree there is no way, given any initial flow, that reducing the flow along one arc would allow the total flow to be increased since the only way that reducing flow along an arc A could increase the total flow is if the flow through A goes to a vertex which the flow through another arc also goes into, which requires a cycle. –  Angela Richardson Mar 28 '12 at 11:28
    
I think using max-flow min-cut theorem is a pretty elegant way to do this; all you have to do is prove that the algorithm terminates (easy), then show how given the final flow you can build a cut with the same value (also not difficult). On this type of graph a much simpler (IMO) greedy algorithm works too; just compute the max flow possible from each vertex in order of increasing height, accounting for edge capacities as you go. –  Sumudu Fernando Oct 3 '12 at 12:07
add comment

1 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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.