0–1 Maximum Flow (0–1 MaxFlow)

Input

A directed graph $G = (V, E)$ with each edge labeled in unary with a capacity $c_i \geq 0$, and two distinguished vertices, source $s$ and sink $t$.

Problem

Find a maximum flow.

Status

Open (Feather [1], Karp, Upfal, and Wigderson [2]).

Remarks

Feather shows the problem of finding the value of the maximum flow to be in $\mathsf{RNC}$ [1]. Karp, Upfal, and Wigderson show how to construct a maximum flow, also in $\mathsf{RNC}$ [2]. Both problems remain in $\mathsf{RNC}$ when capacities are polynomially bounded. Both are $\P$-complete when capacities are arbitrary, see MaxFlow. Karpinski and Wagner show that when $G$ is given by its vertex multiplicity graph representation the Unary Network Flow Problem becomes $\P$-complete [3].