[Model] PartitionIntoCliques

[isPANN]

Motivation

PARTITION INTO CLIQUES (P26) from Garey & Johnson, A1.1 GT15. A classical NP-complete problem useful for reductions. Equivalent to graph coloring on the complement graph: G can be partitioned into K cliques if and only if the complement graph of G is K-colorable. This duality makes it a natural companion to KColoring.

Associated rules:

• [Rule] GRAPH K-COLORABILITY to PARTITION INTO CLIQUES #844: GRAPH K-COLORABILITY → PartitionIntoCliques (complement graph construction, Karp 1972)
• [Rule] PARTITION INTO CLIQUES to MinimumCoveringByCliques #889: PartitionIntoCliques → MinimumCoveringByCliques

Definition

Name: PartitionIntoCliques
Canonical name: PARTITION INTO CLIQUES
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT15

Mathematical definition:

INSTANCE: Graph G = (V,E), positive integer K ≤ |V|.
QUESTION: Can the vertices of G be partitioned into k ≤ K disjoint sets V_1, V_2, . . . , V_k such that, for 1 ≤ i ≤ k, the subgraph induced by V_i is a complete graph?

Variables

• Count: n = |V| variables (one per vertex)
• Per-variable domain: {0, 1, ..., K-1}, indicating which clique the vertex belongs to
• Meaning: Variable i = j means vertex i is assigned to clique group V_j. A valid assignment requires that for every pair of vertices u, v assigned to the same group j, the edge {u, v} is present in E (i.e., each group induces a complete subgraph).

Schema (data type)

Type name: PartitionIntoCliques
Variants: graph topology (graph type parameter G)

Field	Type	Description
graph	SimpleGraph	The undirected graph G = (V, E)
num_cliques	usize	The bound K on the number of cliques

Notes:

• This is a satisfaction (decision) problem: Value = Or, implementing feasibility semantics.
• Key getter methods: num_vertices() (= |V|), num_edges() (= |E|), num_cliques() (= K).
• No weight type is needed (purely structural question).
• Equivalent to KColoring on the complement graph: color classes in the complement are independent sets, which are cliques in G.

Complexity

• Decision complexity: NP-complete (Karp, 1972, where it was called CLIQUE COVER). Transformation from GRAPH K-COLORABILITY via complement graph. Remains NP-complete for all fixed K >= 3. Solvable in polynomial time for K <= 2.
• Best known exact algorithm: O*(2^n) via inclusion-exclusion, since the problem is equivalent to chromatic number computation on the complement graph. The complement construction does not change the number of vertices.
• Concrete complexity expression: "2^num_vertices" (for declare_variants!)
• Special cases:
  • K <= 2: polynomial time
  • Graphs with no K_4 subgraph: remains NP-complete (related to PARTITION INTO TRIANGLES construction)
  • Chordal graphs: polynomial time (Gavril, 1972)
  • Circular arc graphs: polynomial time given arc representation (Gavril, 1974)
  • Comparability graphs: polynomial time (Golumbic, 1977)
  • Perfect graphs: polynomial time (clique cover number equals chromatic number of complement)
• References:
  • R. M. Karp (1972). "Reducibility among combinatorial problems." In Complexity of Computer Computations, Plenum Press.
  • A. Björklund, T. Husfeldt, M. Koivisto (2009). "Set Partitioning via Inclusion-Exclusion." SIAM J. Comput. 39(2), pp. 546-563.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), positive integer K ≤ |V|.
QUESTION: Can the vertices of G be partitioned into k ≤ K disjoint sets V_1, V_2, . . . , V_k such that, for 1 ≤ i ≤ k, the subgraph induced by V_i is a complete graph?
Reference: [Karp, 1972] (there called CLIQUE COVER). Transformation from GRAPH K-COLORABILITY.
Comment: Remains NP-complete for edge graphs [Arjomandi, 1977], for graphs containing no complete subgraphs on 4 vertices (see construction for PARTITION INTO TRIANGLES in Chapter 3), and for all fixed K ≥ 3. Solvable in polynomial time for K ≤ 2, for graphs containing no complete subgraphs on 3 vertices (by matching), for circular arc graphs (given their representation as families of arcs) [Gavril, 1974a], for chordal graphs [Gavril, 1972], for comparability graphs [Golumbic, 1977].

How to solve

• It can be solved by (existing) bruteforce — enumerate all assignments of vertices to K groups and check that each group induces a complete subgraph.
• It can be solved by reducing to integer programming — binary variables x_{v,j} for vertex v in clique j, constraints enforcing partition (each vertex in exactly one group) and clique validity (non-adjacent vertices cannot share a group). Companion rule issue to be filed separately.
• Other: Equivalent to KColoring on complement graph; any graph coloring algorithm applies after complementation.

Example Instance

Instance 1 (YES — partition into cliques exists):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 9 edges, K = 3:

• Edges: {0,1}, {0,2}, {1,2}, {3,4}, {3,5}, {4,5}, {0,3}, {1,4}, {2,5}
• Partition: V_1 = {0, 1, 2}, V_2 = {3, 4, 5}
  • V_1: edges {0,1}, {0,2}, {1,2} all present — K_3 ✓
  • V_2: edges {3,4}, {3,5}, {4,5} all present — K_3 ✓
• Answer: YES (only 2 cliques needed; 66 valid partitions out of 729 total with K=3)

Instance 2 (NO — no partition into K cliques exists):
Graph G with 5 vertices {0, 1, 2, 3, 4} and 5 edges, K = 2:

• Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,0} (a 5-cycle C_5)
• The largest cliques in C_5 are edges (size 2); no triangles exist.
• Any clique covers at most 2 vertices. With K=2, we cover at most 4 vertices; the 5th needs a 3rd clique.
• Example: {0,1} and {2,3} are cliques, but vertex 4 is left uncovered. Clique cover number = 3.
• Answer: NO (0 valid partitions out of 32 with K=2)

Python validation script

from itertools import product

def count_valid(n, edges, K):
    edge_set = set()
    for u, v in edges:
        edge_set.add((u,v)); edge_set.add((v,u))
    count = 0
    for assign in product(range(K), repeat=n):
        valid = True
        for c in range(K):
            members = [v for v in range(n) if assign[v] == c]
            for i in range(len(members)):
                for j in range(i+1, len(members)):
                    if (members[i], members[j]) not in edge_set:
                        valid = False; break
                if not valid: break
            if not valid: break
        if valid: count += 1
    return count

# Instance 1: YES
e1 = [(0,1),(0,2),(1,2),(3,4),(3,5),(4,5),(0,3),(1,4),(2,5)]
assert count_valid(6, e1, 3) == 66
print("Instance 1: 66/729 valid (YES)")

# Instance 2: NO (C5, K=2)
e2 = [(0,1),(1,2),(2,3),(3,4),(4,0)]
assert count_valid(5, e2, 2) == 0
print("Instance 2: 0/32 valid (NO)")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; concrete reduction from KColoring planned
Non-trivial	✅ Pass	Distinct feasibility constraints from all existing problems
Correctness	⚠️ Warn	Minor citation inaccuracy (year/authorship); core claims verified
Well-written	⚠️ Warn	Missing ILP companion issue link; minor notation issue

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

Pass. PartitionIntoCliques does not exist in the codebase. The issue identifies a concrete reduction from KColoring via complement graph construction, connecting it to the existing graph. The problem is one of Karp's original 21 NP-complete problems (listed as "Clique Cover"), making it a valuable addition. Brute-force and ILP solver paths are identified.

Non-trivial

Pass. While PartitionIntoCliques is related to KColoring via complement, it has genuinely different feasibility constraints: it requires partitioning vertices into cliques (complete subgraphs) rather than coloring vertices with independent sets. The existing PartitionIntoTriangles is a special case (fixed clique size 3), not the same problem. No existing problem in the codebase is isomorphic.

Correctness

Warn. Core claims are correct but with a citation inaccuracy:

• NP-completeness (Karp, 1972): Verified. Clique Cover is indeed one of Karp's 21 NP-complete problems, proved via reduction from Graph K-Colorability. The complement-graph duality (clique cover in G = coloring in complement of G) is well-established.
• Complement-graph equivalence: Correct. A set of vertices forms a clique in G iff it forms an independent set in the complement of G, so partition into K cliques in G = K-coloring of the complement.
• Complexity claim issue: The issue cites "Björklund, Husfeldt, Koivisto (2006)" for the O*(2^n) bound. However, at FOCS 2006 these were actually two separate papers: (1) Björklund & Husfeldt, "Inclusion-exclusion algorithms for counting set partitions" (pp. 575–582), and (2) Koivisto, "An O*(2^n) algorithm for graph coloring and other partitioning problems via inclusion-exclusion" (pp. 583–590). The combined 3-author paper "Set Partitioning via Inclusion-Exclusion" appeared in SIAM J. Comput. 2009 (Vol. 39, Issue 2, pp. 546–563), not at FOCS 2006. The O*(2^n) bound itself is correct.
• Special cases: Claims about polynomial-time solvability for K ≤ 2, chordal graphs, circular arc graphs, and comparability graphs are consistent with Garey & Johnson's commentary.

Well-written

Warn. The issue is generally well-written and complete, with the following items to address:

1. Missing ILP companion issue: The "How to solve" section checks the ILP box and describes an ILP formulation, but there is no linked [Rule] PartitionIntoCliques to ILP companion issue in a "Reduction Rule Crossref" section. Per project conventions, if direct ILP solving is claimed, a companion rule issue should be linked.

2. Complexity expression: The complexity section describes O*(2^n) but does not provide the expression in terms of the problem's getter method names (e.g., 2^num_vertices). This should be made explicit for the declare_variants! macro.

3. Example quality: Both examples are correct and verified. Example 1 (YES instance) has 729 total configurations with 66 satisfying assignments — good for round-trip testing. Example 2 (NO instance) correctly demonstrates infeasibility. Both examples are well-worked with step-by-step verification.

4. Minor notation: The definition uses both k (lowercase) and K (uppercase) — "partitioned into k ≤ K disjoint sets". This is consistent with the Garey & Johnson original text, so acceptable, but the Variables section should clarify that each variable takes values in {0, 1, ..., K-1} where K is the num_cliques field.

Recommendations

• Fix the citation to either reference the two separate FOCS 2006 papers or the combined SIAM J. Comput. 2009 journal version (Björklund, Husfeldt, Koivisto, "Set Partitioning via Inclusion-Exclusion", SIAM J. Comput. 39(2):546–563, 2009).
• Add a [Rule] PartitionIntoCliques to ILP companion issue and link it in a "Reduction Rule Crossref" section.
• Add explicit complexity expression: 2^num_vertices for use in declare_variants!.

[isPANN]

Fix-issue changelog

• Citation: Fixed BHK reference from "FOCS 2006" to SIAM J. Comput. 39(2):546-563, 2009.
• Complexity: Added concrete expression "2^num_vertices" for declare_variants!.
• Associated rules: Linked [Rule] GRAPH K-COLORABILITY to PARTITION INTO CLIQUES #844 (KColoring → PartitionIntoCliques) and [Rule] PARTITION INTO CLIQUES to MinimumCoveringByCliques #889 (PartitionIntoCliques → MinimumCoveringByCliques).
• ILP: Added companion rule note.
• Schema notes: Added getter methods.
• Example: Cleaned up Instance 2 reasoning; added exact counts (66/729 and 0/32).
• Added Python validation script.

Applied by /fix-issue.

[isPANN]

Please kindly check the following items (PR #960):

• Paper (PDF): check definition, proof sketch, example figure, and reproducible pred commands
• Implementation (Optional): spot-check the source files changed in this PR for correctness

💬 Join the discussion on Zulip — feel free to ask questions or leave feedback there.