[Model] MaximumDomaticNumber

[isPANN]

Motivation

DOMATIC NUMBER (GT3) from Garey & Johnson, A1.1. The domatic number of a graph is the maximum number of disjoint dominating sets the vertex set can be partitioned into. NP-complete for any fixed K >= 3 (Garey, Johnson, Tarjan 1976b). The domatic number is always >= 1 (the whole vertex set is dominating) and <= δ(G)+1 where δ(G) is the minimum degree. Applications in distributed computing, network reliability, and resource allocation.

Definition

Name: MaximumDomaticNumber
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT3; Garey, Johnson, Tarjan 1976b

Mathematical definition:

INSTANCE: Graph G = (V,E).
OBJECTIVE: Find the maximum k such that V can be partitioned into k disjoint sets V_1, V_2, ..., V_k where each V_i is a dominating set for G (i.e., for every vertex v in V, either v ∈ V_i or v is adjacent to some vertex in V_i).

In other words, find the maximum number of disjoint dominating sets the graph can be partitioned into.

Variables

• Count: n = |V| (one per vertex)
• Per-variable domain: {0, 1, ..., n-1}
• Meaning: The index of the dominating set to which each vertex is assigned. Every part of the partition must satisfy the domination property. The objective is to maximize the number of non-empty parts.

Schema (data type)

Type name: MaximumDomaticNumber
Variants: graph: SimpleGraph

Field	Type	Description
graph	SimpleGraph	The input graph G = (V,E)

Complexity

• Best known exact algorithm: O*(2.695^n) by Riege, Rothe, Spakowski, and Yamamoto (2007, Information Processing Letters 101(3), 101–106) using a polynomial-space algorithm. The general inclusion-exclusion approach of Björklund, Husfeldt, and Koivisto (2009) achieves O*(2^n) but requires exponential space. The problem is NP-complete for any fixed K >= 3 (Garey, Johnson, Tarjan 1976b). For K = 2, the problem is polynomial — a graph has domatic number >= 2 if and only if it has no isolated vertex.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), positive integer K <= |V|.
QUESTION: Can V be partitioned into k >= K disjoint sets V_1, V_2, ..., V_k, such that each V_i is a dominating set for G?

Reference: Transformation from 3-SATISFIABILITY [Garey, Johnson, and Tarjan, 1976b].
Comment: NP-complete for any fixed K >= 3. Domatic number is at least 2 if and only if G has no isolated vertex (a necessary condition).

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all partitions of V; check if all parts are dominating; return the maximum number of parts.)
• It can be solved by reducing to integer programming. (ILP with binary variables x_{v,i} for vertex-to-set assignment and y_i for set usage; partition, domination, and linking constraints; maximize Σ y_i.) See companion issue [Rule] MaximumDomaticNumber to ILP #963.
• Other:

Reduction Rule Crossref

• [Rule] Satisfiability → MaximumDomaticNumber #938 — [Rule] Satisfiability → MaximumDomaticNumber
• [Rule] MaximumDomaticNumber to ILP #963 — [Rule] MaximumDomaticNumber to ILP (direct ILP formulation)

Example Instance

Input:
Graph G = (V, E) with V = {v0, v1, v2, v3, v4, v5} (n = 6).
Edges: {(v0,v1), (v0,v2), (v0,v3), (v1,v4), (v2,v5), (v3,v4), (v3,v5), (v4,v5)}.

Vertex degrees: v0: 3, v1: 2, v2: 2, v3: 3, v4: 3, v5: 3. Minimum degree δ = 2, so domatic number ≤ δ+1 = 3.

Optimal partition into 3 dominating sets:

• V_1 = {v0, v3}: dominates because v1 adj v0 ✓, v2 adj v0 ✓, v4 adj v3 ✓, v5 adj v3 ✓
• V_2 = {v1, v5}: dominates because v0 adj v1 ✓, v2 adj v5 ✓, v3 adj v5 ✓, v4 adj v5 ✓
• V_3 = {v2, v4}: dominates because v0 adj v2 ✓, v1 adj v4 ✓, v3 adj v4 ✓, v5 adj v4 ✓

Assignment: config = [0, 1, 2, 0, 2, 1] (vertex → set index).

Why 4 sets is impossible: With 6 vertices and 4 sets, at least two sets would contain only one vertex. A singleton {v} is a dominating set only if v is adjacent to all other vertices. Since no vertex has degree 5 (= n-1), no singleton dominates, so no 4-partition can work.

Expected Outcome

Optimal value: Max(3) — the maximum domatic number of this graph is 3. There are 6 optimal partitions into 3 dominating sets, 26 valid partitions into 2 sets, and the trivial 1-set partition, giving 3 distinct objective values.

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	❌ Fail	No planned reduction rules mentioned — orphan node
Non-trivial	✅ Pass	Distinct feasibility constraints from existing problems
Correctness	❌ Fail	Complexity claim of O*(3^n) is not the best known; better algorithms exist
Well-written	❌ Fail	Missing Expected Outcome section; no reduction crossrefs

Overall: 1 passed, 0 warnings, 3 failed

---

Usefulness

The problem DomaticNumber does not yet exist in the codebase — good. However, the issue body does not mention any planned reduction rules connecting DomaticNumber to the existing reduction graph. A problem without any planned reduction to/from an existing problem has no value in the reduction graph. At minimum, the issue should state a concrete reduction (e.g., "DomaticNumber reduces from KColoring" or "DomaticNumber reduces to ILP") and ideally link a companion [Rule] issue.

Additionally, the "How to solve" section checks brute-force but does not check ILP. If ILP is viable (and it is — the domatic partition problem has a natural ILP formulation as noted in the issue's own text), the issue should check that box and link a [Rule] DomaticNumber to ILP companion issue.

Non-trivial

DomaticNumber is a genuinely distinct problem:

• vs MinimumDominatingSet: MDS finds a single smallest dominating set; DomaticNumber partitions all vertices into the maximum number of disjoint dominating sets. Different objective, different feasibility constraints.
• vs KColoring: Coloring requires adjacent vertices to differ; domination requires every vertex to be adjacent to a member of its part. Fundamentally different constraints.

No existing problem in the codebase captures this partition-into-dominating-sets structure.

Correctness

Reference verification:

• Garey & Johnson, GT3: Confirmed. DomaticNumber is listed as GT3 in the appendix of Computers and Intractability (1979). The NP-completeness attribution to "Garey, Johnson, Tarjan 1976b" is consistent with the book's convention — the underlying paper is likely "Some Simplified NP-Complete Graph Problems" (Theoretical Computer Science, 1(3), 237–267, 1976).
• "Domatic number >= 2 iff no isolated vertex": Confirmed via Wikipedia and standard references.

Complexity claim — FAIL:
The issue claims the best known algorithm is O*(3^n) via inclusion-exclusion, citing "Björklund, Husfeldt, Koivisto 2009." This is incorrect in two ways:

1. The O*(3^n) bound is the naive set partitioning complexity (enumerate all 3-partitions). Björklund, Husfeldt, and Koivisto (SIAM J. Computing, 2009) actually achieve O*(2^n) for general set partitioning problems using inclusion-exclusion over the zeta transform.

2. For domatic number specifically, even better algorithms exist:

   • Riege, Rothe, Spakowski & Yamamoto (2007): O*(2.695^n) in polynomial space (Information Processing Letters, 101(3), 101–106)
   • van Rooij (2010): O*(2.7139^n) in polynomial space (CIAC 2010, LNCS 6078) — this uses a different technique (inclusion/exclusion meets measure and conquer)

The complexity string should be updated to "2.695^num_vertices" (Riege et al. 2007) or potentially an even better bound if one exists.

Recommendations

• Update the complexity to O*(2.695^n) citing Riege et al. (2007), or O*(2^n) citing Björklund et al. (2009) for the general inclusion-exclusion approach. The 3^n figure is not the state of the art.

Well-written

Missing sections:

1. Expected Outcome: The example provides YES/NO answers but does not give a concrete solution configuration. For the K=2 case, the expected outcome should explicitly state the partition assignment, e.g., "config = [0, 1, 0, 1] meaning v0 -> V_1, v1 -> V_2, v2 -> V_1, v3 -> V_2."
2. Reduction Rule Crossref: No planned reduction rules are mentioned. The issue should identify at least one concrete reduction connecting DomaticNumber to the existing graph (e.g., a [Rule] DomaticNumber to ILP issue).

Example quality:

• The C4 example with K=2 is reasonable for illustrating the concept but is borderline too simple — with 4 vertices and 2 sets, there are only 2^4 = 16 possible partitions (actually 2^4/symmetry, fewer distinct ones). A graph with 5-6 vertices would provide more meaningful round-trip testing.
• The example does demonstrate both a YES and NO case, which is good.

Notation consistency:

• The definition uses both k (lowercase, the actual partition count) and K (uppercase, the threshold). This is consistent with Garey & Johnson's convention but should be clearly distinguished — currently it reads "k >= K" which is correct.

ILP note inconsistency:

• The "How to solve" note mentions "ILP formulation uses binary variables x_{v,i}" but the ILP checkbox is left unchecked. If ILP solving is viable, check the box and link a companion rule issue.

Recommendations

• Add an explicit expected outcome with vertex-to-set assignments for the K=2 case
• Add at least one planned reduction (DomaticNumber -> ILP is the most natural)
• Consider a slightly larger example (5-6 vertices) for better round-trip test coverage
• Check the ILP box in "How to solve" and link a [Rule] DomaticNumber to ILP companion issue

[isPANN]

Converted from decision framing (DomaticNumber with bound K) to optimization framing (MaximumDomaticNumber — maximize disjoint dominating sets). Removed Useless, Wrong, and PoorWritten labels. Companion rule issue: #938 (Satisfiability → MaximumDomaticNumber). Satisfiability already exists in the codebase.