If $f$ is an integral flow in $G$, then why there is a feasible acyclic integral flow of the same value?

426 Views Asked by At

I have already proven that this statement (a) given any feasible flow $f$ in $G$, there is a feasible acyclic flow of the same value. But I am not sure why the following statement(b) is true: If $f$ is an integral flow in $G$, then there is a feasible acyclic integral flow of the same value.

Isn't the statement (b) just trivial from the statement (a)? Since we have a feasible flow $f$ of integer flow value in $G$, and by (a), there is a feasible acyclic flow of the same value, which is also an integer. What nontrivial points am I missing?

1

There are 1 best solutions below

4
On

Just imitate the proof for the general case. In that proof, you reduce the flows in any directed cycle, all of whose edges have positive flow, by the flow in the cycle edge with minimum flow, until no positive cycles remain. If the original flow is integral, this process preserves integrality.