Approximating the Domatic Number

The domatic number problem is that of partitioning the vertices of an undirected graph into the maximum number of disjoint dominating sets. Let n denote the number of vertices in a graph, delta the minimum degree, and DELTA the maximum degree. Trivially, the domatic number is at most ( delta + 1). We show that every graph has a domatic partition with (1-o(1)( delta + 1)/ln n dominating setss, 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 also show this to be essentially best possible. Namely, extending the approximation hardness of set cover by combining multi-prover protocols with zero-knowledge techniques, we show that for every epsilon > 0, a (1 - epsilon )ln n-approximation implies that NP C_ DTIM E (n sup O(log 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 show that every graph has a domatic partition with (1 - o(1))( delta + 1)/ln DELTA dominating sets, where the "o(1)" term goes to zero as DELTA increases. This can be turned into an efficient algorithm that produces a domatic partition of OMEGA ( delta /ln DELTA ) sets.