An improved approximation algorithm for requirement cut

This note presents improved approximation guarantees for the requirement cut   problem: given an nn-vertex edge-weighted graph G=(V,E)G=(V,E), and gg groups of vertices X1,…,Xg⊆VX1,…,Xg⊆V with each group XiXi having a requirement riri between 0 and |Xi||Xi|, the goal is to find a minimum cost set of edges whose removal separates each group XiXi into at least riri disconnected components. We give a tight Θ(logg)Θ(logg) approximation ratio for this problem when the underlying graph is a tree, and show how this implies an O(logk⋅logg)O(logk⋅logg) approximation ratio for general graphs, where k=|∪i=1gXi|≤n.