Approximating the domatic number

Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء


The domatic number problem is that of partitioning the vertices of a graph into the maximum number of disjoint dominating sets. Let n denote the number of vertices in a graph, δ the minimum degree, and Δ the maximum degree. Trivially, the domatic number is at most (δ + 1). We show that every graph has a domatic partition with (1 -o(1))(δ + 1)/ln n sets, and moreover, that such a domatic partition can be found in polynomial time. This implies a (1 + o(1))ln n approximation algorithm for domatic number. We show that to be essentially best possible. Namely, extending the approximation hardness of set cover by combining multiprover protocols with zero-knowledge techniques, we show that for every ε > 0, a (1 - ε)ln n-approximation implies that NP ⊆ DTIME(nlog log n). This makes domatic number the first natural maximization problem (known to the authors) that is provably approximable to within polylogarithmic factors but no better. We also give a refined algorithm that gives a domatic partition of Ω(δ/ln Δ) sets. This implies an O(ln Δ) approximation for domatic number. We suspect that the true constant hidden by the Ω notation should be 1. As a step towards confirming this, we show that every graph of girth at least five and 5 large enough has domatic number at least (1 - o(1))δ/ln Δ.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفProceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000
عدد الصفحات10
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2000
الحدث32nd Annual ACM Symposium on Theory of Computing, STOC 2000 - Portland, OR, الولايات المتّحدة
المدة: ٢١ مايو ٢٠٠٠٢٣ مايو ٢٠٠٠

سلسلة المنشورات

الاسمProceedings of the Annual ACM Symposium on Theory of Computing
رقم المعيار الدولي للدوريات (المطبوع)0737-8017


!!Conference32nd Annual ACM Symposium on Theory of Computing, STOC 2000
الدولة/الإقليمالولايات المتّحدة
المدينةPortland, OR


أدرس بدقة موضوعات البحث “Approximating the domatic number'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا