On Flows in Simple Bidirected and Skew-Symmetric Networks

We consider a simple directed network. Results of Karzanov, Even, and Tarjan show that the blocking flow method constructs a maximum integer flow in this network in $O(m\min(m^{1/2},n^{2/3}))$ time (hereinafter, $n$ denotes the number of nodes, and $m$ the number of arcs or edges). For the bidirected case, Gabow proposed a reduction to solve the maximum integer flow problem in $O(m^{3/2})$ time. We show that, with a variant of the blocking flow method, this problem can also be solved in $O(mn^{2/3})$ time. Hence, the gap between the complexities of directed and bidirected cases is eliminated. Our results are described in the equivalent terms of skew-symmetric networks. To obtain the time bound of $O(mn^{2/3})$, we prove that the value of an integer $s$–$s'$ flow in a skew-symmetric network without parallel arcs does not exceed $O(Un^2/d^2)$, where $d$ is the length of the shortest regular $s$–$s'$ path in the split network and $U$ is the maximum arc capacity. We also show that any acyclic integer flow of value $v$ in a skew-symmetric network without parallel arcs can be positive on at most $O(n\sqrt v)$ arcs.