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

## Petr Kolman and Christian Scheideler

Abstract:

Given an integer h, a graph $G = (V, E)$ with arbitrary positive edge capacities and k pairs of vertices $(s_1,t_1),(s_2, t_2),\dots,(s_k,t_k)$, called terminals, an h-route cut is a set $F \subset 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 flows (take h = 1). The main result of this paper is an $O(h^{5}2^{2h}(h+log k)^2)$-approximation algorithm for the minimum h-route cut problem in the case that $s_1 = s_2 =\dots= s_k$, 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