Volume 4 (2008) Article 1 pp. 1-20

Single Source Multiroute Flows and Cuts on Uniform Capacity Networks

by Henning Bruhn, Jakub Černý, Alexander Hall, Petr Kolman, and Jiří Sgall

Received: September 6, 2007
Published: April 16, 2008
DOI: 10.4086/toc.2008.v004a001

Abstract: [Plain Text Version]

For an integer h ≥ 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 ∈ V and k sinks t₁,…, t_k ∈ V corresponding to k commodities; we denote it ℑ = (s;t₁,…,t_k). In the single source multicommodity multiroute flow problem, we are given an instance ℑ = (s;t₁,…,t_k) and an integer h ≥ 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 ℑ = (s;t₁,…,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 ≥ 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 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 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 ℑ is a set of edges F ⊆ 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.