Approximating the domatic number

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

Research output: Contribution to journalArticlepeer-review

125 Scopus citations

Abstract

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, δ 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.

Original languageEnglish (US)
Pages (from-to)172-195
Number of pages24
JournalSIAM Journal on Computing
Volume32
Issue number1
DOIs
StatePublished - Jan 2003

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Approximation algorithms
  • Domatic number
  • Domination
  • Probabilistic analysis

Fingerprint

Dive into the research topics of 'Approximating the domatic number'. Together they form a unique fingerprint.

Cite this