| Abstract | A set of vertices in a graph is a dominating set if every vertex outside the set hasa 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, δ the
minimum degree, and ∆ the maximum degree.
We show that every graph has a domatic partition with (1 − o(1))(δ + 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
δ+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 ϵ > 0, a (1 − ϵ) ln n-approximation implies that NP ⊆ DTIME(nO(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))(δ + 1)/ ln ∆ dominating
sets, where the “o(1)” term goes to zero as ∆ increases. This can be turned into an efficient algorithm
that produces a domatic partition of Ω(δ/ ln ∆) sets.
|
