Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

Denna tjänst avvecklas 2026-01-19. Läs mer här (länk)

MAXIMUM DOMATIC PARTITION

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A partition of V into disjoint sets $V_1,V_2,\ldots,V_k$ such that each $V_i$ is a domatinating set of G.
• MEASURE: Cardinality of the partition, i.e., the number of disjoint subsets $V_i$.

  
  

• Good News: Approximable within $(1+o(1))\ln \vert V\vert$ [155].
• Bad News: Not approximable within $(1-\varepsilon )\ln \vert V\vert$, for any $\varepsilon >0$, unless $NP \subseteq \mbox{\sc Dtime}(\vert V\vert^{\log\log \vert V\vert})$ [155].
• Comment: The problem is also approximable within $3 \ln \Delta$, where $\Delta$ is the maximum degree, and is not approximable within $(1 - \varepsilon ) \ln \Delta$, for any $\varepsilon >0$ under the same hypothesis. The bad news also hold for split graphs and bipartite graphs. The problem is approximable within 4 on circular-arc graphs [371].
• Garey and Johnson: GT3