Minimum cost circulation problem with bounded number of edges 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)&gt; 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.
After I posted the question in cstheory, I received an answer there. 


  Your problem is NP-Hard and even hard to approximate via easy reductions from Steiner tree problem. Look at the following paper for more information. dl.acm.org/citation.cfm?doid=1077464.1077470.