Integral Biflow Maximization

Abstract

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\to {\mathbb{Z}}_{+}$ be a capacity function, and let $\mathcal{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:\mathcal{P}\to {\mathbb{R}}_{+}$ such that ${\sum }_{e\in Q\in \mathcal{P}}f(Q)\le c(e)$ for all $e\in E$, whose value is defined to be ${\sum }_{Q\in \mathcal{P}}f(Q)$. A bicut in $G$ is a subset $K$ of $E$ that contains at least one edge from each member of $\mathcal{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.

27 pages, 5 figures