Approximating the domatic number
A set of vertices in a graph is a dominating set if every vertex outside the set has a neighbor in the set. 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, delta the minimum degree, and Delta the maximum degree. We show that every graph has a domatic partition with (1 - o(1)) (delta + 1)/ln n dominating 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, since the domatic number is always at most delta + 1. We also show this 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 epsilon > 0, a (1 - epsilon) ln n-approximation implies that N P subset of or equal to DTIME(n(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.
domatic number domination approximation algorithms probabilistic analysis