Homologous Flow (HF)

Input

A directed graph $G = (V, E)$ with each edge $(v, w)$ labeled by a lower and upper bound on flow capacity $l(v, w)$, $u(v, w)$ $\geq 0$ and two distinguished vertices, source $s$ and sink $t$.

Problem

Is there a feasible flow in the network?

Definitions

A feasible flow is one in which the flow assigned to each arc falls within the lower and upper bounds for the arc. A homologous flow is a flow in which pairs of edges are required to have the same flow.

Status

$\P$-complete via $\LOGSPACE$ reductions (Itai [1]).

Remarks

The reduction to show hardness is from $[-1,1]$-LE, see LE.