Theory of Computing
-------------------
Title     : Single Source Multiroute Flows and Cuts on Uniform Capacity Networks
Authors   : Henning Bruhn, Jakub Cerny, Alexander Hall, Petr Kolman, and Jiri Sgall
Volume    : 4
Number    : 1
Pages     : 1-20
URL       : http://www.theoryofcomputing.org/articles/v004a001

Abstract
--------

For an integer h > 0, 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,...,t_k \in V  corresponding to  k  commodities; we denote it 
I = (s;t_1,...,t_k).   In the  *single source multicommodity multiroute 
flow problem*, we are given an instance  I = (s;t_1,...,t_k)  and an 
integer  h > 0, 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  I = (s;t_1,...,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 > 1.  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 to 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 $t_i$'s. 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  I  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.