{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:34Z","timestamp":1787337574689,"version":"build-2736575974"},"reference-count":37,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2002,1]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>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 &gt; 0$, a $(1 - \\epsilon)\\ln n$-approximation implies that $NP \\subseteq 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.<\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1137\/s0097539700380754","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"172-195","source":"Crossref","is-referenced-by-count":124,"title":["Approximating theDomatic Number"],"prefix":"10.1137","volume":"32","author":[{"given":"Uriel","family":"Feige","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guy","family":"Kortsarz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","volume-title":"The probabilistic method","author":"Alon Noga","year":"1992"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90006-K"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020402"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF01584535"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(85)90025-3"},{"key":"R7","unstructured":"P. Erdo\u02dds and L. Lov\u00e1sz,\n                      Problems and results on 3\u2010chromatic hypergraphs and some related questions\n                      , in Infinite and Finite Sets, Vol. II, Colloq. Math. Soc. J\u00e1nos Bolyai 11, A. Hajnal et al., eds., North\u2013Holland, Amsterdam, 1975, pp. 609\u2013627."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90061-1"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"U. Feige, M. M. Halld\u00f3rsson, and G. Kortsarz,\n                      Approximating the domatic number\n                      , in Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 134\u2013143.","DOI":"10.1145\/335305.335321"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"R12","unstructured":"S. Fujita,\n                      On the performance of greedy algorithms for finding maximum r\u2010configurations\n                      , in Proceedings of Korea\u2010Japan Joint Workshop on Algorithms and Computation (WAAC), Seoul National University, Seoul, 1999, pp. 92\u201399."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196311328"},{"key":"R14","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"R16","volume-title":"Domination in graphs","author":"Haynes Teresa","year":"1998"},{"key":"R17","unstructured":"T. W. Haynes, S. T. Hedetniemi, and P. J. Slater.\n                      Fundamentals of Domination in Graphs\n                      , Marcel Dekker, New York, 1998."},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80044-9"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90054-X"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Sanjeev Khanna, Madhu Sudan, David Williamson, A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction, ACM, New York, 1999, 11\u2013201715619","DOI":"10.1145\/258533.258538"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)90026-4"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1145\/185675.306789"},{"key":"R25","unstructured":"F. MacWilliams and N. Sloane,\n                      The Theory of Error Correcting Codes\n                      , North\u2013Holland, Amsterdam, 1983."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00118-W"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"M. Naor, L. Schulman, and A. Srinivasan,\n                      Splitters and near\u2010optimal derandomization\n                      , in Proceedings of the 36th Annual IEEE Symposium on Foundations of Computer Science, 1995, pp. 182\u2013191.","DOI":"10.1109\/SFCS.1995.492475"},{"key":"R28","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(81)90081-5"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90115-C"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1007\/BF01202286"},{"key":"R32","first-page":"173","volume":"5","author":"Kratochv\u00edl Jan","year":"1998","journal-title":"Nordic J. Comput."},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"R34","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"R35","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90184-1"},{"key":"R36","unstructured":"A. Srinivasan,\n                      Domatic partitions and the Lov\u00e1sz local lemma\n                      , in Proceedings of the Twelfth Annual ACM\u2010SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2001, pp. 922\u2013923."},{"key":"R37","first-page":"145","volume":"33","author":"Zelinka Bohdan","year":"1983","journal-title":"Math. Slovaca"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539700380754","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:18:20Z","timestamp":1787336300000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539700380754"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,1]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2002,1]]}},"alternative-id":["10.1137\/S0097539700380754"],"URL":"https:\/\/doi.org\/10.1137\/s0097539700380754","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,1]]}}}