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 to reduce the cost of at most K arcs. In this paper, 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 NP-completeness and inapproximability, even on directed acyclic graphs. On the positive side, we identify three polynomial 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