The Taub Faculty of Computer Science Events and Talks

We consider the REQUIREMENT CUT problem, where given an undirected graph G = (V, E) equipped with non-negative edge weights c , and g groups of vertices X1, . , Xg in V each equipped with a requirement ri, the goal is to find a collection of edges F in E, with total minimum weight, such that once F is removed from G in the resulting graph every Xi is broken into at least ri 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. We present an approximation for the problem, our algorithm is based on a new configuration linear programming relaxation for the problem, which is accompanied by a remarkably simple randomized rounding procedure.