[Model] MaximumAchromaticNumber

[isPANN]

Motivation

ACHROMATIC NUMBER (P16) from Garey & Johnson, A1.1 GT5. The achromatic number of a graph is the maximum number of colors in a complete proper coloring — a proper coloring where every pair of color classes is connected by at least one edge. NP-complete (Yannakakis and Gavril, 1980). Useful in graph theory and network design.

Associated rules:

• [Rule] MINIMUM MAXIMAL MATCHING to MaximumAchromaticNumber #846: MinimumMaximalMatching → MaximumAchromaticNumber (NP-completeness proof)

Definition

Name: MaximumAchromaticNumber
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT5

Mathematical definition:

INSTANCE: Graph G = (V,E).
OBJECTIVE: Find a partition of V into disjoint sets V_1, V_2, ..., V_k that maximizes k, such that each V_i is an independent set for G (no two vertices in V_i are joined by an edge) and such that for each pair of distinct sets V_i, V_j, there exists an edge in E between some vertex in V_i and some vertex in V_j (completeness).

In other words, find a complete proper coloring that maximizes the number of colors used.

Variables

• Count: |V| (one per vertex)
• Per-variable domain: {0, 1, ..., |V|−1}
• Meaning: The color class assigned to each vertex. The coloring must be proper (adjacent vertices get different colors) and complete (every pair of color classes has at least one edge between them). The objective is to maximize the number of distinct colors used.

Schema (data type)

Type name: MaximumAchromaticNumber
Variants: graph: SimpleGraph

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

Notes:

• This is an optimization problem: Value = Max<usize>.
• Key getter methods: num_vertices() (= |V|), num_edges() (= |E|).

Complexity

• Decision complexity: NP-complete (Yannakakis and Gavril, 1980; G&J cites 1978 preprint). Transformation from MINIMUM MAXIMAL MATCHING. NP-complete even for complements of bipartite graphs, cographs, interval graphs, and trees.
• Best known exact algorithm: O*(K^n) where n = |V| and K is the achromatic number, by brute-force enumeration. For fixed K, solvable in linear time.
• Concrete complexity expression: "num_vertices^num_vertices" (for declare_variants!; brute-force with K ≤ |V|)
• Approximation: Within O(|V| / √(log |V|)).
• References:
  • M. Yannakakis, F. Gavril (1980). "Edge Dominating Sets in Graphs." SIAM J. Appl. Math. 38(3), pp. 364-372. (G&J cites a 1978 preprint.)

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), positive integer K ≤ |V|.
QUESTION: Does G have achromatic number K or greater, i.e., is there a partition of V into disjoint sets V_1, V_2, . . . , V_k, k ≥ K, such that each V_i is an independent set for G (no two vertices in V_i are joined by an edge in E) and such that, for each pair of distinct sets V_i, V_j, V_i ∪ V_j is not an independent set for G?
Reference: [Yannakakis and Gavril, 1978]. Transformation from MINIMUM MAXIMAL MATCHING.
Comment: Remains NP-complete even if G is the complement of a bipartite graph and hence has no independent set of more than two vertices.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all vertex colorings; for each, check properness and completeness; maximize number of colors used.)
• It can be solved by reducing to integer programming. (Binary variables x_{v,c} for vertex v assigned color c; properness constraints on adjacent vertices; completeness constraints requiring each color pair to have a connecting edge; maximize number of used colors. Companion rule issue to be filed separately.)
• Other:

Example Instance

Input: Cycle graph C_6 on 6 vertices:
V = {0, 1, 2, 3, 4, 5}, E = {(0,1), (1,2), (2,3), (3,4), (4,5), (5,0)}

Optimal coloring (3 colors): [0, 1, 2, 0, 1, 2]

• Proper: no adjacent vertices share a color ✓
• Complete: colors (0,1) on edge (0,1) ✓, colors (1,2) on edge (1,2) ✓, colors (0,2) on edge (2,3) ✓

Optimal value: Max(3) — the achromatic number of C_6 is 3.

No 4-color complete proper coloring exists (verified exhaustively: 0 valid out of 1296 assignments with 4 colors). With K=2, there are 2 valid colorings, and with K=3 there are 24.

Python validation script

from itertools import product

edges = [(0,1),(1,2),(2,3),(3,4),(4,5),(5,0)]
edge_set = set(edges) | set((b,a) for a,b in edges)

for K in [2, 3, 4]:
    count = 0
    for assign in product(range(K), repeat=6):
        proper = all(assign[u] != assign[v] for u,v in edges)
        if not proper: continue
        used = set(assign)
        if len(used) < K: continue
        complete = all(
            any((assign[u]==c1 and assign[v]==c2) or (assign[u]==c2 and assign[v]==c1)
                for u,v in edges)
            for c1 in used for c2 in used if c1 < c2
        )
        if complete: count += 1
    print(f"K={K}: {count} valid complete proper colorings")

# Expected: K=2: 2, K=3: 24, K=4: 0
# Achromatic number = 3

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	⚠️ Warn	ILP solving claimed but no companion [Rule] AchromaticNumber to ILP issue linked
Non-trivial	✅ Pass	Distinct feasibility constraints from KColoring (completeness condition)
Correctness	⚠️ Warn	Reference year discrepancy; complexity claim is brute-force only
Well-written	❌ Fail	Missing Expected Outcome section; naming convention violation; problem framing ambiguity

Overall: 1 passed, 2 warnings, 1 failed

---

Usefulness

The problem does not exist in the codebase (pred show AchromaticNumber fails). It is a classical NP-complete problem from Garey & Johnson (A1.1 GT5) and adds a genuinely different node to the reduction graph compared to KColoring.

However, the issue does not mention any concrete reduction rule connecting this problem to existing problems in the graph, beyond checking the "reduces to integer programming" box. No companion [Rule] AchromaticNumber to ILP issue is linked in a "Reduction Rule Crossref" section. The skill requires: "if ILP is claimed, a direct [Rule] <ProblemName> to ILP companion issue must be linked." This is a Warn rather than a Fail because the ILP path is plausible and easily addressed.

Non-trivial

The achromatic number problem has genuinely different feasibility constraints from all existing problems in the codebase. While KColoring asks "can the graph be properly colored with at most K colors?", the achromatic number asks for a complete coloring: a proper coloring where every pair of distinct color classes is connected by at least one edge. This completeness condition is a substantively different constraint. Pass.

Correctness

3a - Definition correctness: The mathematical definition is well-formed and matches the standard definition of achromatic number / complete coloring from the literature.

3b - Complexity verification: The issue claims O*(K^n) brute-force complexity. This is a reasonable bound for enumerating all K-colorings of n vertices, but it is not a dedicated algorithm -- it is just brute force. No specialized exact algorithm is cited. This is acceptable as a starting point but the issue should acknowledge that no better exact algorithm is known (or cite one if it exists).

3c - Reference verification: The issue cites "Yannakakis and Gavril (1978)". The actual publication is:

M. Yannakakis and F. Gavril, "Edge Dominating Sets in Graphs," SIAM Journal on Applied Mathematics, Vol. 38, No. 3, pp. 364-372, 1980.

The NP-completeness of achromatic number appears as a corollary in this paper, proved via reduction from Minimum Maximal Matching. The year "1978" in the issue likely comes from G&J citing a preprint or conference version. The G&J book itself references "[Yannakakis and Gavril, 1978]" which may refer to a technical report. This is a minor discrepancy but worth noting for accuracy.

3d - Approximation claim: The issue states "approximable within O(|V| / sqrt(log |V|))". This claim should be cited with a specific reference. The approximation literature on achromatic number includes work by Kortsarz and Krauthgamer (1998, ESA) and Chaudhary and Vishwanathan (1997), but no specific citation is given.

Well-written

4a - Information completeness:

Section	Status
Motivation	Present but minimal
Name	❌ Naming convention violation -- optimization problems must use Maximum/Minimum prefix per CLAUDE.md. The Compendium of NP Optimization Problems lists this as "Maximum Achromatic Number". The name should be MaximumAchromaticNumber.
Reference	Present (G&J)
Definition	Present and well-formed
Variables	Present
Schema	Present
Complexity	Present (brute-force only, no concrete expression like K^num_vertices)
How to solve	Present
Example Instance	Present and correct
Expected Outcome	❌ Missing -- no clearly separated expected outcome. The example narrative mentions "the answer is YES for K = 3" but does not provide a structured expected outcome with a concrete solution and brief justification as required.

4b - Definition completeness: The definition is precise and directly from G&J. However, there is an ambiguity in problem framing: the issue presents this as a decision problem ("QUESTION: Does G have achromatic number K or greater?") but does not clarify whether the implementation should be a feasibility problem (Value = Or) or an optimization problem (Value = Max). Given the natural formulation as maximization and the naming convention requiring Maximum prefix, the issue should explicitly state this is an optimization problem that maximizes K, or clarify it is a feasibility problem parameterized by K.

4c - Symbol consistency: Symbols are generally consistent. The definition uses V_1, V_2, ..., V_k with lowercase k but the Schema uses uppercase K for num_colors. Minor inconsistency.

4d - Example quality: The C6 example with K=3 is correct and non-trivial. Verification confirms 24 feasible complete 3-colorings out of 729 total assignments. However:

• For a decision/feasibility framing, the example should also show a case where the answer is NO (e.g., K=4 on C6) with explanation.
• The note about K=4 is present but confused ("C6 has chromatic number 2, so we can use at most 3 colors in a complete coloring since with 4 colors we cannot guarantee..."). The reasoning is hand-wavy; a clearer argument would help.

Recommendations

• Rename to MaximumAchromaticNumber to follow the optimization naming convention, or explicitly frame as a feasibility problem with Value = Or if the decision version is intended.
• Add Expected Outcome section with a concrete solution: e.g., "Optimal achromatic number: 3. Witness: [0, 1, 2, 0, 1, 2]."
• Link a companion issue [Rule] MaximumAchromaticNumber to ILP or remove the ILP checkbox.
• Add a concrete complexity expression in terms of problem parameters, e.g., num_colors^num_vertices.
• Cite the approximation result with a specific paper reference.
• Clarify the year: Yannakakis and Gavril (1980) for the published version, or note that G&J cites a 1978 preprint.

[isPANN]

Converted from decision framing (AchromaticNumber with bound K) to optimization framing (MaximumAchromaticNumber — maximize colors in a complete proper coloring). Removed PoorWritten label. Companion rule issue: #939 (MinimumMaximalMatching → MaximumAchromaticNumber). Note: MinimumMaximalMatching is not yet in the codebase.

[isPANN]

Fix-issue changelog

• Associated rules: Linked [Rule] MINIMUM MAXIMAL MATCHING to MaximumAchromaticNumber #846 (MinimumMaximalMatching → MaximumAchromaticNumber).
• Schema notes: Added Value = Max<usize> and getter methods.
• Complexity: Fixed Yannakakis-Gavril year (1978 preprint → 1980 published). Added concrete expression "num_vertices^num_vertices".
• ILP: Added companion rule note.
• Example: Added expected outcome with exhaustive verification (K=2: 2, K=3: 24, K=4: 0).
• Added Python validation script.

Applied by /fix-issue.