Abstrakt
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), \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 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=\cdots=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.