  We investigate the complexity and approximability of the budget-constrained
minimum cost flow problem, which is an extension of the traditional minimum
cost flow problem by a second kind of costs associated with each edge, whose
total value in a feasible flow is constrained by a given budget B. This problem
can, e.g., be seen as the application of the {\epsilon}-constraint method to
the bicriteria minimum cost flow problem. We show that we can solve the problem
exactly in weakly polynomial time $O(\log M \cdot MCF(m,n,C,U))$, where C, U,
and M are upper bounds on the largest absolute cost, largest capacity, and
largest absolute value of any number occuring in the input, respectively, and
MCF(m,n,C,U) denotes the complexity of finding a traditional minimum cost flow.
Moreover, we present two fully polynomial-time approximation schemes for the
problem on general graphs and one with an improved running-time for the problem
on acyclic graphs.
