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. © 2016 Wiley Periodicals, Inc. NETWORKS, Vol. 69(1), 67–82 2017