Approximating Requirement Cut via a Configuration LP

Abstract

We consider the {Requirement Cut} problem, where given an undirected graph G = (V,E) equipped with non-negative edge weights c:E → R_{+}, and g groups of vertices X₁,…,X_{g} ⊆ V each equipped with a requirement r_i, the goal is to find a collection of edges F ⊆ E, with total minimum weight, such that once F is removed from G in the resulting graph every X_{i} is broken into at least r_{i} 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 O(log{n}log{R}) for the problem, which was subsequently improved to O(log{g} log{k}) by Gupta, Nagarajan and Ravi [Operations Research Letters`10] (here R = ∑ _{i = 1}^g r_i and k = |∪ _{i = 1}^g X_i |). We present an approximation of O(Xlog{R} √{log{k}}log{log{k}}) for {Requirement Cut} (here X = max _{i = 1,…,g} {|X_i|}). Our approximation in general is incomparable to the above mentioned previous results, however when all groups are not too large, i.e., X = o((√{log{k}}log{g})/(log{R}log{log{k}})), it is better. Our algorithm is based on a new configuration linear programming relaxation for the problem, which is accompanied by a remarkably simple randomized rounding procedure.