Closing the Complexity Gap for Exact Domatic Number at Three and Four
2026-07-10 • Computational Complexity
Computational ComplexityDiscrete Mathematics
AI summaryⓘ
The authors solved a puzzle about graphs, which are like networks of dots connected by lines, related to how they can be split into groups where each group covers the entire graph. Previous work showed the problem is very hard for groups of size 5 or more, but it was unclear for sizes 3 and 4. The authors created a method that turns a logical formula into a graph that clearly shows if the formula can be true or not, by having the graph split into either 4 or 2 groups. Using this, they proved that for sizes 3 and 4, the problem is just as complex as for larger sizes, completing the understanding of how hard this problem is for all group sizes 3 and up.
domatic numbergraph theoryDP-completeness3SAT reductiongraph partitionNP-completenesscomputational complexitygraph gadgetsdomination in graphsexact domatic number problem
Authors
Holger Spakowski
Abstract
The exact domatic-number problem asks, for a fixed integer k, whether a given graph G satisfies dom(G) = k. Riege and Rothe proved DP-completeness for every fixed k >= 5, while the cases k = 3 and k = 4 remained open. We close this classification gap. The main ingredient is a polynomial-time reduction from 3SAT whose output graphs have domatic number 4 in the satisfiable case and domatic number 2 in the unsatisfiable case; in particular, the reduction never produces a graph of domatic number 3. This directly realizes the route suggested by Riege and Rothe for closing the remaining cases. Together with a simpler three-versus-two reduction, this yields DP-completeness of Exact-3-DNP and Exact-4-DNP. The proofs are constructive and give explicit graph gadgets whose local domination constraints encode truth assignments and clause satisfaction. The soundness arguments show conversely that any sufficiently large domatic partition enforces the intended consistency conditions and therefore yields a satisfying assignment. Consequently, Exact-k-DNP is DP-complete for every fixed k >= 3, completing the fixed-value classification from k = 3 onward.