TY - JOUR

T1 - Complexity and approximability of the maximum flow problem with minimum quantities

AU - Thielen, Clemens

AU - Westphal, Stephan

PY - 2013/9

Y1 - 2013/9

N2 - We consider the maximum flow problem with minimum quantities (MFPMQ), which is a variant of the maximum flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound (a minimum quantity), which may depend on the arc. This problem has recently been shown to be weakly NP -complete even on series-parallel graphs. In this article, we provide further complexity and approximability results for MFPMQ and several special cases. We first show that it is strongly NP -hard to approximate MFPMQ on general graphs (and even bipartite graphs) within any positive factor. On series-parallel graphs, however, we present a pseudo-polynomial time dynamic programming algorithm for the problem. We then study the case that the minimum quantity is the same for each arc in the network and show that, under this restriction, the problem is still weakly NP -complete on general graphs, but can be solved in strongly polynomial time on series-parallel graphs. On general graphs, we present (2-1/λ)-approximation algorithm for this case, where λ denotes the common minimum quantity of all arcs.

AB - We consider the maximum flow problem with minimum quantities (MFPMQ), which is a variant of the maximum flow problem where the flow on each arc in the network is restricted to be either zero or above a given lower bound (a minimum quantity), which may depend on the arc. This problem has recently been shown to be weakly NP -complete even on series-parallel graphs. In this article, we provide further complexity and approximability results for MFPMQ and several special cases. We first show that it is strongly NP -hard to approximate MFPMQ on general graphs (and even bipartite graphs) within any positive factor. On series-parallel graphs, however, we present a pseudo-polynomial time dynamic programming algorithm for the problem. We then study the case that the minimum quantity is the same for each arc in the network and show that, under this restriction, the problem is still weakly NP -complete on general graphs, but can be solved in strongly polynomial time on series-parallel graphs. On general graphs, we present (2-1/λ)-approximation algorithm for this case, where λ denotes the common minimum quantity of all arcs.

KW - approximation algorithms

KW - computational complexity

KW - maximum flow problem

KW - minimum quantities

UR - http://www.scopus.com/inward/record.url?scp=84882453738&partnerID=8YFLogxK

U2 - 10.1002/net.21502

DO - 10.1002/net.21502

M3 - Article

AN - SCOPUS:84882453738

SN - 0028-3045

VL - 62

SP - 125

EP - 131

JO - Networks

JF - Networks

IS - 2

ER -