We consider the Requirement Cut problem, where given an undirected graph  equipped with non-negative edge weights , and  groups of vertices  each equipped with a requirement , the goal is to find a collection of edges , with total minimum weight, such that once  is removed from  in the resulting graph every  is broken into at least  connected components. Requirement Cut captures multiple classic cut problems in graphs, e.g., Multicut, Multiway Cut, Min k-Cut, Steiner k-Cut, Steiner Multicut, and Multi-Multiway Cut. Nagarajan and Ravi [Algoritmica‘10] presented an approximation of  for the problem, which was subsequently improved to  by Gupta, Nagarajan and Ravi [Operations Research Letters‘10] (here  and ). They also proved that there is a hardness of approximation of  when the graph is a tree. Thus, providing a tight approximation when the graph is a tree. In both these works, the main approach to solving (RC) in general graphs is first to formulate a linear programming relaxation which finds a suitable spreading metric over the vertices of , then transform the metric into a tree metric, and finally round the solution on the tree. In the second work, an additional greedy combinatorial approach is presented. In this approach the algorithm repeatedly finds cuts that (approximately) minimize the ratio between their cost and the number of groups they separate. This algorithm also yields an approximation of  for (RC).

We present an approximation of  for Requirement Cut (here ). Our algorithm is based on a new configuration linear programming relaxation for the problem, which is accompanied by a remarkably simple randomized rounding procedure.