Approximate Duality of Multicommodity Multiroute Flows and Cuts

Petr Kolman

KAM MFF UK

Abstract

Given an integer $h$, a graph $G=(V,E)$ and $k$ pairs of vertices $(s_1,t_1), (s_2,t_2), \ldots, (s_k,t_k)$, called terminals, an $h$-route cut is a set $F\subseteq E$ of edges such that after the removal of the edges in $F$ no pair $s_i-t_i$ is connected by $h$ edge disjoint paths (i.e., the connectivity of every $s_i-t_i$ pair is at most $h-1$ in $(V,E\setminus F)$). The $h$-route cut is a natural generalization of the classical cut problem for multicommodity flow (take $h=1$). The main result of this paper is an $O(h^7 2^{2h} \log^3 k)$-approximation algorithm for the minimum $h$-route cut problem. As a corollary of it we obtain an approximate duality theorem for multiroute multicommodity flows and cuts. This answers an open question posted in several previous papers dealing with cuts for multicommodity multiroute problems. Key ingredient of the proof is a generalization of the ball growing