Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case

Petr Kolman and Christian Scheideler


Given an integer h, a graph with arbitrary positive edge capacities and k pairs of vertices , called terminals, an h-route cut is a set of edges such that after the removal of the edges in F no pair is connected by h edge-disjoint paths (i.e., the connectivity of every pair is at most in . The h-route cut is a natural generalization of the classical cut problem for multicommodity flows (take h = 1). The main result of this paper is an -approximation algorithm for the minimum h-route cut problem in the case that , called the single source case. As a corollary of it we obtain an approximate duality theorem for multiroute multicommodity flows and cuts with a single source. This partially answers an open question posted in several previous papers dealing with cuts for multicommodity multiroute problems.

Guest: Christian Scheideler
Host: Shantanu Das