Graph problem... Let $D=(V,A)$ be a directed graph, and $s,t \in V$. Let $f:A \to \mathbb{R}_+$ be an $s$-$t$ flow of value $\beta$, show that there exists an $s$-$t$ flow $f':A\to\mathbb{Z}_+$ of value $\lceil\beta\rceil$, such that $\lfloor f(a) \rfloor \leq f'(a)\leq \lceil f(a) \rceil$ for all $a \in A$.
I was trying to construct one by starting from modifying a min-cut, and the capacity function such that an application of maxflow-mincut theorem gives an integer solution if flow whose value agrees the modified min-cut...but it is not clear how it should go....
 A: Here is an algorithm that modifies the flow $f$ so that it would satisfy the condition:


*

*total flow is $\ge\lceil\beta\rceil$;

*the flow on each edge is either rounded up or rounded down to an integer.


Algorithm:
Set the edges with fractional flow the floating state.

While there is a floating edge e
  Set P := e, the path consisting only e
  Extend P as much as possible using only floating edges
    until one of the following happens
    1. P contains a cycle C
    2. P is a path from s to t
  If case 1 then
     Designate a direction d on C
     Set E[+] := all edges on C whose direction consistent with d.
     Set E[-] := all edges on C whose direction inconsistent with d.
     Increase the flow on edges in E[+] by c and decrease E[-] by c
       where c is the smallest real number so that
       at least of the edges in C will have integral flow.
  If case 2 then
     Set the direction on P from s to t
     Do the same thing as in case 1
  Update the states for all edges
End while

Some explanation and caveats:


*

*For any floating edge $e=(u,v)$, there is always another floating edge $e'$ adjacent to $e$ at $v$ unless $v\in\{s,t\}$.

*Every time, we have at least one less floating edge, and so the algorithm will terminate at certain stage.

*When the algorithm terminates, all edges have integral flow and the total flow can only increase. One can see this by looking at case 2.

*To get exactly $\lceil{\beta}\rceil$ as the total flow, one only needs to be careful in case 2. If the $s$-to-$t$ direction on $P$ would result in the total flow greater than $\lceil{\beta}\rceil$, one can instead choose the $t$-to-$s$ direction meanwhile guaranteeing that the resulting total flow is bigger than $\lceil\beta\rceil-1$.

