Minimum cost flows with minimum quantities

We consider a variant of the well-known minimum cost flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound. The problem was recently shown to be weakly NPNP-complete even on series-parallel graphs. We start by showing that the problem is strongly NPNP-complete and cannot be approximated in polynomial time (unless P=NPP=NP) up to any polynomially computable function even when the graph is bipartite and the given instance is guaranteed to admit a feasible solution. Moreover, we present a pseudo-polynomial-time exact algorithm and a fully polynomial-time approximation scheme (FPTAS) for the problem on series-parallel graphs.

► Proof of strong NP-completeness of Min Cost Network Flow with Minimum Quantities. ► Pseudo-polynomial time dynamic programming algorithm on series-parallel graphs. ► Fully polynomial time approximation scheme (FPTAS) on series-parallel graphs.