Premium
The budgeted minimum cost flow problem with unit upgrading cost
Author(s) -
Büsing Christina,
Koster Arie,
Kirchner Sarah,
Thome Annika
Publication year - 2017
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21724
Subject(s) - treewidth , minimum cost flow problem , mathematics , flow network , directed graph , bounded function , reduction (mathematics) , steiner tree problem , computer science , combinatorics , time complexity , mathematical optimization , graph , pathwidth , line graph , mathematical analysis , geometry
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