#StackBounty: #algorithms #network-flow Minimum cost circulation problem with bounded number of edges

Bounty: 50

During an article I am writing, I encountered the following problem:
Let $N=(G=(V,E),W,C)$ be a network with a graph $G$, a weight function $W:Eto R$ and an integer capacity function $C:E to N$.
Find a circulation $f$ with minimal cost $W(f)$ such that the number of edges used by the circulation (i.e., edges $e$ s.t. $f(e)> 0$) is smaller than or equal to a parameter $r$.

Note that if $r=|E|$, the problem is simply the well-known circulation, which is solvable in polynomial time.

I tried to search “Google Scholar” and use variations of the cycle canceling (and other min cost flow) algorithms to solve the problem but with no successes.


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.