5
$\begingroup$

Suppose we have a circulation problem (with only one commodity), where all lower bounds, upper bounds, and costs are integers. Are we guaranteed that if there is a solution, then there is an integral solution? Is there an algorithm that can find one in polynomial time?

For standard network flow, we know that there is a max flow that is integral, and there are polynomial-time algorithms that can find such an integral flow. I'm wondering if the same is true for circulation problems, which are a generalization of max-flow.

$\endgroup$
4
$\begingroup$

Circulation problems are not just a generalization of max-flow, there is a reduction backwards as well. Suppose we have some directed graph $G = (V, E)$ with edge costs, capacities, and lower bounds.

Any edge $u \to v$ in $G$ with we can replace with two nodes $s, t$ and two edges $s \to v$ and $u \to t$ where one of the edges has the original cost, capacities, and lower bounds and the other is free and unlimited. Call this graph $G'(e)$, where $e = u\to v$ is the edge that was replaced.

Then if a flow with a certain cost exists in $G'(\cdot)$, it must also exist as a circulation in $G$ with the same cost. Vice versa, if a circulation exists in $G$ and it uses edge $u \to v$, then that flow also exists in $G'(u\to v)$ with the same cost.

Therefore to solve the circulation problem we can pick an arbitrary edge $e$, calculate $G'(e)$ and use a traditional network flow algorithm to find the optimal flow. By the traditional arguments, this optimal flow is integral. We then pick another edge (avoiding edges that were part of a previous optimal flow) and repeat, keeping the best solution, until no more unknown edges are left.

Since in the worst case this adds a factor of $|E|$ to the complexity of the polynomial complexity, this is still polynomial. And of course the optimum from all integral flows found is itself integral.

To handle the lower bounds on the edges of $G'$, one can either note that the linear programming constraint matrix is unimodular (see these MIT lecture notes), from which it follows that there exists an integral solution if there is any solution; or one can use a standard reduction to eliminate the lower bounds (see, e.g., Ahuja et al, Network Flows, page 39) and then solve with a standard algorithm for network flow.

$\endgroup$
7
  • $\begingroup$ Circulation problems also come with a lower bound on each edge. How are the lower bounds reflected in $G'$? $\endgroup$ – D.W. Oct 25 '20 at 23:41
  • $\begingroup$ @D.W. The lower bounds are copied to one of the edges (say, $s \to v$) like all the other parameters (cost, capacity, etc). Then to get your 'traditional' guarantees, min-cost max-flow with (integer) lower bounds can be transformed into one without lower bounds, see Ahuja et al, Network Flows, page 39. $\endgroup$ – orlp Oct 26 '20 at 1:14
  • $\begingroup$ @D.W. For what it's worth, you can probably find a much more direct route to your desired claims (probably in that very same book), this is just one chain of transformations I know that works. $\endgroup$ – orlp Oct 26 '20 at 1:18
  • $\begingroup$ @D.W. A more direct route is in these MIT lecture notes by noting that the LP constraint matrix $A = \begin{pmatrix}N\\\hline I\\\hline -I\end{pmatrix}$ they describe is total unimodular, and is also capable of expressing the circulation problem. This guarantees that the feasible polytope of the problem is integral, and thus any poly-time LP solver that returns vertices of the polytope will give you the guarantees you want. $\endgroup$ – orlp Oct 26 '20 at 1:30
  • $\begingroup$ Perfect! That was exactly what I was missing. Any interest in editing your answer to incorporate that information, or would you like me to do that? $\endgroup$ – D.W. Oct 26 '20 at 3:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.