Graph problem...

Question

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

Answer 1

Here is an algorithm that modifies the flow $f$ so that it would satisfy the condition:

1. total flow is $\ge\lceil\beta\rceil$;
2. 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:

1. For any floating edge $e=(u,v)$, there is always another floating edge $e'$ adjacent to $e$ at $v$ unless $v\in\{s,t\}$.
2. Every time, we have at least one less floating edge, and so the algorithm will terminate at certain stage.
3. 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.
4. 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$.