Abstract
We consider the {Requirement Cut} problem, where given an undirected graph G = (V,E) equipped with nonnegative 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 kCut}, {Steiner kCut}, {Steiner Multicut}, and {MultiMultiway 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.
BibTeX  Entry
@InProceedings{schwartz_et_al:LIPIcs:2020:12656,
author = {Roy Schwartz and Yotam Sharoni},
title = {{Approximating Requirement Cut via a Configuration LP}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {53:153:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12656},
URN = {urn:nbn:de:0030drops126560},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.53},
annote = {Keywords: Approximation, Requirement Cut, Sparsest Cut, Metric Embedding}
}
Keywords: 

Approximation, Requirement Cut, Sparsest Cut, Metric Embedding 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020) 
Issue Date: 

2020 
Date of publication: 

11.08.2020 