Approximating the Minimum-Cost Maximum Flow is P-Complete

We show that it is impossible, in NC, to approximate the value of the minimumcost maximum flow unless P = NC. Keywords: Theory of computation, P-complete, minimum-cost flow, maximum flow. 1 Introduction Once a problem is proved to be P-complete, it is generally believed that there exists no NC or RNC algorithm to solve it exactly 1 . Therefore, the next important question becomes how well can it be approximated in NC or RNC? In this note we establish an interesting contrast between the parallel complexity of two related P-Complete problems, the maximum-flow problem and the minimum-cost maximum flow problem. We show that despite the fact that one can approximate the value of a maximum flow arbitrarily closely in RNC, approximating the value of the minimum-cost maximum flow within a factor of C, the maximum cost in the network, is P-Complete. Our proof also shows that this is true for networks with C polynomial in the size of the network, when the costs of the network are expressed ..