3
$\begingroup$

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

1 Answers 1

2

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

  • 0
    So simple but also very clear... Tha$n$k you :), I will have to increase my $p$roblem solving skills.2011-12-19