The parallel complexity of finding a blocking flow in a 3-layer network (Q1119019)

A flow in a network with a source s and a sink t is a blocking flow if every path from s to t contains a saturated edge. The authors show that the problem of finding the lex-first blocking flow in an acyclic network is log-space complete for P even if the network is restricted to be a 3- layer network. Inspite of this the authors demonstrate that there is a random NC algorithm for finding an arbitrary blocking flow in a 3-layer network.