Approximation Algorithms for Requirement Cut on Graphs

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to a requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X₁...X_g\⊆ V , each with a requirement r_i between 0 and |X_i|. The goal is to find a minimum cost set of edges whose removal separates each group ∣X_i∣ into at least r_i disconnected components. We give an O(log n log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is a natural Ω (log g) hardness of approximation for the requirement cut problem.