Lexicographically First Blocking Flow (LFBF)

Input

A directed acyclic graph $G = (V, E)$ represented by fixed ordered adjacency lists with each edge $e$ labeled by a capacity $c(e) \geq 0$, and two distinguished vertices, source $s$ and sink $t$.

Problem

Is the value of the lexicographically first blocking flow odd?

Definitions

A blocking flow is a flow in which every path from $s$ to $t$ has a saturated edge — an edge whose flow is equal to its capacity. The lexicographically first blocking flow is the flow resulting from the standard sequential depth-first search blocking flow algorithm.

Status

$\P$-complete (Anderson and Mayr [1]).

Remarks

The reduction is similar to the one for MaxFlow. The problem of finding the lexicographically first blocking flow in a three layered network is also $\P$-complete. A three layered network is one in which all source to sink paths have length three. Cheriyan and Maheshwari also give an $\mathsf{RNC}$ algorithm for finding a blocking flow in a three layered network [2], also see BF3.

Goldberg and Tarjan give a parallel algorithm for finding a blocking flow in an acyclic network [3]. Their algorithm runs in parallel time $O(n \log n)$ and uses $m$ processors on an EREW-PRAM, where the network has $n$ vertices and $m$ edges.