  Let $G=(V,E)$ be a graph with four distinguished vertices, two sources $s_1,
s_2$ and two sinks $t_1,t_2$, let $c:\, E \rightarrow \mathbb Z_+$ be a
capacity function, and let ${\cal P}$ be the set of all simple paths in $G$
from $s_1$ to $t_1$ or from $s_2$ to $t_2$. A biflow (or $2$-commodity flow) in
$G$ is an assignment $f:\, {\cal P}\rightarrow \mathbb R_+$ such that $\sum_{e
\in Q \in {\cal P}}\, f(Q) \le c(e)$ for all $e \in E$, whose value is defined
to be $\sum_{Q \in {\cal P}}\, f(Q)$. A bicut in $G$ is a subset $K$ of $E$
that contains at least one edge from each member of ${\cal P}$, whose capacity
is $\sum_{e\in K}\, c(e)$. In 1977 Seymour characterized, in terms of forbidden
structures, all graphs $G$ for which the max-biflow (integral) min-bicut
theorem holds true (that is, the maximum value of an integral biflow is equal
to the minimum capacity of a bicut for every capacity function $c$); such a
graph $G$ is referred to as a Seymour graph. Nevertheless, his proof is not
algorithmic in nature. In this paper we present a combinatorial polynomial-time
algorithm for finding maximum integral biflows in Seymour graphs, which relies
heavily on a structural description of such graphs.
