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.

Let $G=(V,E)$ be an acyclic directed graph with source $s \in V$ and sink $t \in V$, $n=|V|,m=|E|$. Is it always true that for every blocking flow $f$ we have $\text{value}(f)\geq \frac{c}{n}$, where $c$ is the value of a maximum $s$-$t$-flow?

I have been sitting at this one for quite a few hours and can't seem to figure it out. As a corollary to a flow decomposition theorem I know that there exist an $s$-$t$ augmenting path which induces a flow of $\frac{c}{m}$ but unfortunately this is not good enough as in directed acyclic graphs $m$ is not tightly bounded by $n$. I also read about Dinic's algorithm and that it shows that $n$ blocking flows are sufficient to generate a maximum flow, but I don't see how I could apply this to the question as these flows are in the residual graph $G_f$. Also it odes not need that $G$ is acyclic.

(A blocking flow $f$ is a flow where $s$ and $t$ are disconnected in the residual graph $G_f$ or alternatively where every $s$-$t$ path contains at least one saturated edge).

share|improve this question

1 Answer 1

up vote 2 down vote accepted

Let me see if I get it. Take any blocking flow $F$ and for every vertex $v\in V$ denote by $A_v$ the sum of capacities of saturated edges in $F$ coming out of $v$. The absence of cycles implies that the value of the flow $F$ is at least $\max_v A_v$ (you cannot pump more through one vertex than your whole amount going through because the pumping is irreversible). Now assume that the maximal flow has value more than $\sum_v A_v$. Shutting down one edge cannot diminish the maximal flow value by more than the capacity of that edge (we can always decompose any flow into a combination of paths with positive coefficients). Thus, shutting down all edges saturated in $F$ will diminish the value of the maximal flow by at most $\sum_v A_v$ and we'll have something trickling from $s$ to $t$ despite we've shut down all paths, which is absurd. Now, it remains to note that $\sum_v A_v\le |V|\max_v A_v$.

share|improve this answer
    
So simple but also very clear... Thank you :), I will have to increase my problem solving skills. –  Listing Dec 19 '11 at 15:03

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.