Search code examples
algorithmgraph-algorithmnetwork-flow

Min-Cost Flow Integrality Theorem


The min-cost flow problem's integrality theorem states that given "integral data", there is always an integral solution to the problem that corresponds to minimum-cost flow. The notion of integral data is slightly confusing to me as most papers, tutorials say that the demands, supplies and capacities should be integral. Now, a capacity constraint is typically represented as

l_i  <=  c_i  <= u_i

where l_i is the lower bound on the capacity of edge i, and u_i is the upper bound. In order for the integrality theorem to hold, is it enough that l_i and u_i are integers? The doubt comes from the fact that this doesn't necessarily mean that the flows are always integers themselves as for example, for l_i = 0, u_i = 1, edge i can have a flow of 0.5.


Solution

  • Yes, that is exactly what the integrality theorem says.

    If all of the l_i and u_i are integers, and any feasible solution exists, then there must exist a solution where all flows are integers.

    This does not mean that all solutions must be integers. Just that at least one will be.