The budgeted minimum cost flow problem with unit upgrading cost

The budgeted minimum cost flow problem (BMCF(K)) with unit upgrading costs extends the classical minimum cost flow problem by allowing one to reduce the cost of at most K arcs. In this article, we consider complexity and algorithms for the special case of an uncapacitated network with just one source. By a reduction from 3‐SAT we prove strong N P ‐completeness and inapproximability, even on directed acyclic graphs. On the positive side, we identify three polynomially solvable cases: on arborescences, on so‐called tree‐like graphs, and on instances with a constant number of sinks. Furthermore, we develop dynamic programs with pseudo‐polynomial running time for the BMCF(K) problem on (directed) series‐parallel graphs and (directed) graphs of bounded treewidth.