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
עמודים134-143
מספר עמודים10
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2000
אירוע32nd Annual ACM Symposium on Theory of Computing, STOC 2000 - Portland, OR, ארצות הברית
משך הזמן: 21 מאי 200023 מאי 2000

סדרות פרסומים

שםProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (מודפס)0737-8017

כנס

כנס32nd Annual ACM Symposium on Theory of Computing, STOC 2000
מדינה/אזורארצות הברית
עירPortland, OR
תקופה21/05/0023/05/00

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Approximating the domatic number'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי