Integral Biflow Maximization

Let $G=(V,E)$ be a graph with four distinguished vertices, two sources s₁, s₂ and two sinks t₁,t₂, let c:\, E → Z₊ be a capacity function, and let P be the set of all simple paths in G from s₁ to t₁ or from s₂ to t₂. A biflow (or $2$-commodity flow) in G is an assignment f:\, P→ R₊ such that ∑_e ∈ Q ∈ P\, f(Q) ≤ c(e) for all e ∈ E, whose value is defined to be ∑_Q ∈ P\, f(Q). A bicut in G is a subset K of E that contains at least one edge from each member of P, whose capacity is ∑e∈ 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.