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.