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.
Article
View The Budgeted Minimum Cost Flow Problem with Unit Upgrading Cost