# Minimum cost circulation problem with bounded number of edges

Note: the question was taken from https://cs.stackexchange.com/questions/95479/minimum-cost-circulation-problem-with-bounded-number-of-edges

Since there was no answer in that forum (even after setting multiple bounties), I am trying also here.

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:E\to 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.