The multi-multiway cut problem

Adi Avidor, Michael Langberg

نتاج البحث: نشر في مجلةمقالةمراجعة النظراء


In this paper, we define and study a natural generalization of the multicut and multiway cut problems: the minimum multi-multiway cut problem. The input to the problem is a weighted undirected graph G = (V, E) and k sets S1, S2, ..., Sk of vertices. The goal is to find a subset of edges of minimum total weight whose removal completely disconnects each one of the sets S1, S2, ..., Sk, i.e., disconnects every pair of vertices u and v such that u, v ∈ Si, for some i. This problem generalizes both the multicut problem, when | Si | = 2, for 1 ≤ i ≤ k, and the multiway cut problem, when k = 1. We present an approximation algorithm for the multi-multiway cut problem with an approximation ratio which matches that obtained by Garg, Vazirani, and Yannakakis on the standard multicut problem. Namely, our algorithm has an O (log k) approximation ratio. Moreover, we consider instances of the minimum multi-multiway cut problem which are known to have an optimal solution of light weight. We show that our algorithm has an approximation ratio substantially better than O (log k) when restricted to such "light" instances. Specifically, we obtain an O (log LP)-approximation algorithm for the problem when all edge weights are at least 1 (here LP denotes the value of a natural linear programming relaxation of the problem). The latter improves the O (log LP log log LP) approximation ratio for the minimum multicut problem (implied by the work of Seymour and Even et al.).

اللغة الأصليةالإنجليزيّة
الصفحات (من إلى)35-42
عدد الصفحات8
دوريةTheoretical Computer Science
مستوى الصوت377
رقم الإصدار1-3
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 31 مايو 2007

ملاحظة ببليوغرافية

Funding Information:
The authors would like to thank Uri Zwick for many helpful discussions. The first author’s work was supported in part by THE ISRAEL SCIENCE FOUNDATION founded by The Israel Academy of Sciences and Humanities.


أدرس بدقة موضوعات البحث “The multi-multiway cut problem'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا