Technical Report MSC-2021-33

Title: Approximation Algorithm for Requirement Cut
Authors: Yotam Sharoni
Supervisors: Roy Schwartz
PDFCurrently accessibly only within the Technion network
Abstract: We consider the Requirement Cut problem, where given an undirected graph $G=\left(V,E\right)$ equipped with non-negative edge weights $c:E\rightarrow\mathbb{R_{+}}$, and $g$ groups of vertices $X_{1},\ldots,X_{g}\subseteq V$ each equipped with a requirement $r_i$, the goal is to find a collection of edges $F\subseteq 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, {\em 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=\sum _{i=1}^g r_i$ and $k = |\cup _{i=1}^g X_i |$). They also proved that there is a hardness of approximation of $\Omega (\log{g})$ 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 $V$, 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 $O(\log{n}\log{R})$ for (RC). We present an approximation of $O(X\log{R} \sqrt{\log{k}}\log{\log{k}})$ for Requirement Cut (here $X=\max _{i=1,\ldots,g}\{ |X_i|\}$).

Our algorithm is based on a new configuration linear programming relaxation for the problem, which is accompanied by a remarkably simple randomized rounding procedure.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the MSC technical reports of 2021
To the main CS technical reports page

Computer science department, Technion