Maximum Flow (MaxFlow)

Input

A directed graph $G = (V, E)$ with each edge $e$ labeled by an integer capacity $c(e) \geq 0$, two distinguished vertices, source $s$ and sink $t$, and a value $f$.

Problem

Is there a feasible flow of value $f$, that is, is the value of the maximum flow into the sink greater than or equal to $f$?

Definitions

See [1] and [2].

Status

$\P$-complete (Goldschlager, Shaw, and Staples [3], Lengauer and Wagner [4]).

Remarks

The first $\P$-completeness proof for a decision problem derived from Maximum Flow was for the problem of determining whether the flow is odd or even [3]. See Dinic [1] or Ford and Fulkerson [2] for polynomial time algorithms. The reduction from AM2CVP produces exponential edge capacities in $G$. In a network with edge capacities expressed in unary, computing the magnitude of the maximum flow is in $\mathsf{RNC}^2$ (Feather [5]) and a method for finding the flow in $\mathsf{RNC}$ is also known (Karp, Upfal, and Wigderson [6]).

If the network is restricted to being acyclic, MaxFlow remains $\P$-complete (Ramachandran [7]). Flows in planar networks can be computed in $\NC$ (Johnson [8], Johnson and Venkatesan [9]). Two Commodity Flow (2CF) is defined similar to MaxFlow except there are two sources and two sinks, and there are two separate flow functions for the commodities. Since MaxFlow is a special case of 2CF and 2CF is in $\P$ by results of Itai [10] and Khachian [11], it follows that 2CF is $\P$-complete. Itai defined several other variants of 2CF that are also $\P$-complete. They are defined below. $(l, u)$-2CF is a restricted form of 2CF in which there are lower and upper bounds on the capacity of each edge. Selective $(l, u)$-2CF is defined to be a 2CF with lower and upper bounds on the sum of the two flows on each edge. Stein and Wein show that, although there is an $\mathsf{RNC}$ algorithm to approximate maximum flow, approximating the minimum cost maximum flow is $\P$-complete [12].