Published: April 16, 2008

**Keywords:**graphs, multi-route flow, paths, multicommodity flow, connectivity, approximation algorithms

**Categories:**combinatorial optimization, networks, network flow, graphs, algorithms, approximation algorithms

**ACM Classification:**G.2.2, F.2.2

**AMS Classification:**68R10, 05C38, 68W25, 90C27

**Abstract:**
[Plain Text Version]

For an integer $h\geq 1$, an *elementary $h$-route flow* is a flow
along $h$ edge disjoint paths between a source and a sink, each path
carrying a unit of flow, and a single commodity *$h$-route flow* is a
non-negative linear combination of elementary $h$-route flows. An instance of a
*single source multicommodity flow problem* for a graph $G=(V,E)$
consists of a source vertex $s\in V$ and $k$ sinks $t_1,\ldots, t_k\in V$
corresponding to $k$ commodities;
we denote it $\CI=(s;t_1,\ldots,t_k)$. In the *single source
multicommodity multiroute flow problem*, we are given an instance
$\CI=(s;t_1,\ldots,t_k)$ and an integer $h\geq 1$, and the objective is to
maximize the total amount of flow that is transferred from the source to
the sinks so that the capacity constraints are obeyed and, moreover, the
flow of each commodity is an $h$-route flow.

We study the relation between classical and multiroute single source flows on undirected networks with uniform capacities and we provide a tight bound. In particular, we prove the following result. Given an instance $\CI=(s;t_1,\ldots,t_k)$ such that each $s-t_i$ pair is $h$-connected, the maximum classical flow between $s$ and the $t_i$ is at most $(2-2/h)$-times larger than the maximum $h$-route flow between $s$ and the $t_i$ and this is the best possible bound for $h\geq 2$. This, as we show, is in contrast to the situation of general multicommodity (i.e., multiple sources or non-uniform capacities) multiroute flows that are up to $k(1-1/h)$-times smaller than their classical counterparts.

Furthermore, we introduce and investigate *duplex flows* defined
so that the capacity constraints on edges are applied
independently for each direction. We show that for networks with
uniform capacities and for instances as above the maximum classical
flow between $s$ and the $t_i$ is the same as the maximum $h$-route
duplex flow between $s$ and the $t_i$. Moreover, the total flow on each
edge in the duplex flow can be restricted to $(2-2/h)C$, where $C$ is
the capacity of each edge.

As a corollary, we establish a max-flow min-cut theorem for the single
source multicommodity multiroute flow and cut. An *$h$-disconnecting
cut* for $\CI$ is a set of edges $F\subseteq E$ such that for each $i$, the
maximum $h$-route flow between $s$ and $t_i$ is zero.
We show that the maximum $h$-route flow is within $2h-2$ of the minimum
$h$-disconnecting cut, independently of the number of commodities; we also
describe a $(2h-2)$-approximation algorithm for the minimum
$h$-disconnecting cut problem.