[Model] MinimumCoveringByCliques

[isPANN]

Motivation

COVERING BY CLIQUES (P28) from Garey & Johnson, A1.1 GT17. A classical NP-hard problem useful for reductions. The edge clique cover number is a fundamental graph invariant equivalent to the intersection number, connecting this problem to intersection graph theory.

Associated rules:

• [Rule] PARTITION INTO CLIQUES to MinimumCoveringByCliques #889: PartitionIntoCliques → MinimumCoveringByCliques
• [Rule] COVERING BY CLIQUES to MinimumIntersectionGraphBasis #848: MinimumCoveringByCliques → MinimumIntersectionGraphBasis

Definition

Name: MinimumCoveringByCliques
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT17

Mathematical definition:

INSTANCE: Graph G = (V,E).
OBJECTIVE: Find the minimum number of subsets V_1, V_2, ..., V_k of V such that each V_i induces a complete subgraph (clique) of G and such that for each edge {u,v} ∈ E there is some V_i that contains both u and v.

The objective value is Min(k), the minimum number of cliques needed to cover all edges.

Variables

• Count: |E| (one per edge)
• Per-variable domain: {0, 1, ..., |E|-1} (index of the clique covering that edge; upper bound since at most |E| cliques are ever needed)
• Meaning: Variable i indicates which clique covers edge i. The assignment is valid if every edge is assigned to a clique such that all edges assigned to the same clique index form a subset of edges within some clique in G. The objective minimizes the number of distinct clique indices used.

Schema (data type)

Type name: MinimumCoveringByCliques
Variants: (SimpleGraph, One) — unweighted, simple graph input

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

Notes:

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

Complexity

• Decision complexity: NP-hard (Kou, Stockmeyer, and Wong, 1978; Orlin, 1976). Transformation from PARTITION INTO CLIQUES. NP-hard even for planar graphs and graphs with maximum degree 6.
• Best known exact algorithm: FPT parameterized by solution size k with a kernel of at most 2^k vertices, yielding 2^(2^O(k)) · n^O(1) time. Double-exponential dependence on k is necessary assuming ETH (Cygan et al., 2016). Brute-force: O(k^|E|) time.
• Concrete complexity expression: "num_edges^num_edges" (for declare_variants!; brute-force bound with k ≤ |E|)
• References:
  • L.T. Kou, L.J. Stockmeyer, C.K. Wong (1978). "Covering Edges by Cliques with Regard to Keyword Conflicts among in a File." Comm. ACM 21(2), pp. 135-139.
  • M. Cygan, M. Pilipczuk, M. Pilipczuk (2016). "Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal." ACM Trans. Algorithms 12(2), Article 21.

Extra Remark

Full book text:

INSTANCE: Graph G = (V,E), positive integer K ≤ |E|.
QUESTION: Are there k ≤ K subsets V_1, V_2, . . . , V_k of V such that each V_i induces a complete subgraph of G and such that for each edge {u,v} ∈ E there is some V_i that contains both u and v?
Reference: [Kou, Stockmeyer, and Wong, 1978], [Orlin, 1976]. Transformation from PARTITION INTO CLIQUES.

How to solve

• It can be solved by (existing) bruteforce. (Enumerate all possible clique covers; return the one with the fewest cliques.)
• It can be solved by reducing to integer programming. (Binary variables x_C for each maximal clique C; constraint that each edge is covered by at least one selected clique; minimize Σ x_C. Companion rule issue to be filed separately.)
• Other: (TBD)

Example Instance

Input:
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 9 edges:
Edges: {0,1}, {1,2}, {2,3}, {3,0}, {0,2}, {4,0}, {4,1}, {5,2}, {5,3}

Optimal clique cover (4 cliques):

• C_1 = {0, 1, 2}: covers {0,1}, {1,2}, {0,2}
• C_2 = {0, 2, 3}: covers {2,3}, {3,0}
• C_3 = {0, 1, 4}: covers {4,0}, {4,1}
• C_4 = {2, 3, 5}: covers {5,2}, {5,3}

All 9 edges covered. Optimal value: Min(4).

No 3-clique cover exists (verified by exhaustive search over all 13 cliques of size ≥ 2). The minimum is tight.

Suboptimal cover (5 cliques): Replace C_1 with two smaller cliques: {0,1} and {1,2} and {0,2}. This uses 6 cliques — suboptimal.

Python validation script

from itertools import combinations

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

# Verify 4-clique cover
cliques = [{0,1,2}, {0,2,3}, {0,1,4}, {2,3,5}]
covered = set()
for c in cliques:
    members = list(c)
    for a in range(len(members)):
        for b in range(a+1, len(members)):
            assert (members[a], members[b]) in edge_set
            covered.add((min(members[a],members[b]), max(members[a],members[b])))
assert covered == edges_norm
print("4-clique cover verified")

# Verify no 3-clique cover exists
all_cliques = []
for size in range(2, 7):
    for combo in combinations(range(6), size):
        s = set(combo)
        if all((a,b) in edge_set for a in s for b in s if a != b):
            all_cliques.append(s)

found_3 = any(
    set().union(*(
        {(min(a,b),max(a,b)) for a in all_cliques[i] for b in all_cliques[i] if a<b}
    for i in c3)) == edges_norm
    for c3 in combinations(range(len(all_cliques)), 3)
)
assert not found_3
print("No 3-cover exists. Minimum is 4.")

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem not yet in reduction graph; connected via #889 and #848
Non-trivial	✅ Pass	Distinct feasibility constraint (edge clique cover) from all existing problems
Correctness	⚠️ Warn	Minor reference year inaccuracies; complexity lacks concrete expression
Well-written	❌ Fail	Missing Expected Outcome; ILP claimed without companion issue link; messy example

Overall: 2 passed, 1 warning, 1 failed

---

Usefulness

The problem CoveringByCliques does not exist in the codebase. It is a classical NP-complete problem (GT17 from Garey & Johnson). The issue is connected to the reduction graph via planned rules: #889 (PartitionIntoCliques -> CoveringByCliques) and #848 (CoveringByCliques -> IntersectionGraphBasis). The motivation field references Garey & Johnson and mentions the connection to intersection graph theory. Pass.

Non-trivial

This is genuinely a distinct problem. It asks for an edge clique cover of minimum size, which differs from existing problems in the codebase:

• Not the same as MaximumClique (finding a single largest clique)
• Not the same as PartitionIntoCliques (vertex partition into cliques, not edge covering)
• Not the same as BicliqueCover (covering with bicliques, not cliques)

The feasibility constraint (every edge must be covered by at least one of K cliques) is unique. Pass.

Correctness

References verified:

• Kou, Stockmeyer, and Wong: The paper "Covering edges by cliques with regard to keyword conflicts and intersection graphs" exists in Communications of the ACM, 1978. The NP-completeness claim is correct. Verified.
• Orlin: The issue references "Orlin, 1976" but the paper "Contentment in graph theory: Covering graphs with cliques" was communicated in 1977 (published in Indagationes Mathematicae). Minor year discrepancy -- this appears to come directly from G&J's own citation, so it may reflect the original book's reference style.
• Cygan et al.: The issue says "Cygan et al., 2015" but the SIAM Journal on Computing version was published in 2016 (Vol. 45, No. 1, pp. 67-83). The conference version appeared at SODA 2013. Neither year matches 2015. Minor year error.
• The claim about NP-completeness for planar graphs and maximum degree 6 is from Kou et al. 1978. Verified.

Complexity expression:
The complexity section provides only asymptotic expressions: 2^(2^O(K)) * n^O(1) and O(K^|E|). The project requires concrete complexity expressions in terms of problem parameters (e.g., num_cliques^num_edges), not Big-O notation. The declare_variants! macro needs a literal expression string like "num_cliques^num_edges", not an O-notation bound.

Overall: Warn (references are real and support the claims, but years are slightly off and complexity expression is not concrete enough for implementation).

Well-written

Failures:

1. Missing Expected Outcome: The template requires a concrete valid/satisfying solution with justification. The example shows cliques that cover edges but does not explicitly state "Answer: YES" with a clear, clean presentation. The example is also messy -- it starts with K=3, demonstrates failure, then revises to K=4. A clean example should present a single well-chosen instance with its solution.

2. ILP companion issue not linked: The "How to solve" section checks "It can be solved by reducing to integer programming" but there is no linked [Rule] CoveringByCliques to ILP companion issue and no "Reduction Rule Crossref" section. Per the template, when ILP solvability is claimed, a direct reduction rule issue must be linked.

3. Complexity expression not concrete: As noted above, the complexity section needs a concrete expression suitable for declare_variants! (e.g., "num_cliques^num_edges" for the brute-force bound), not asymptotic O-notation.

4. Example quality issues:

   • The example is self-contradictory: it claims K=3, then shows the solution fails, then revises to K=4. A good example should present one clean instance.
   • The "house graph" claim is questionable -- 6 vertices with that edge set is not a standard house graph.
   • The example should include at least 2 suboptimal feasible configurations to be round-trip testable (e.g., show that K=5 also works but K=4 is the minimum, or show a different valid 4-clique cover).

5. Pervasive ~~ Unverified ~~ markers: The Variables, Schema, Complexity, and Example sections all carry unverified markers, suggesting the content has not been reviewed by the issue author.

Warnings:

• The variable formulation (one variable per edge, domain {0,...,K-1}) is valid but somewhat unusual. A more standard formulation uses binary variables x_{i,j} indicating whether clique j contains vertex i, which maps more naturally to ILP. This is not a failure but worth reconsidering for implementation clarity.

Recommendations

• Replace the messy K=3-then-K=4 example with a single clean instance. Consider a smaller graph (e.g., a path P4 with 3 edges, K=2) as a simple example, plus the current 6-vertex instance as a richer one.
• Add a concrete complexity expression: "num_cliques^num_edges" captures the brute-force bound K^|E|.
• Link or create a [Rule] CoveringByCliques to ILP issue for the ILP solving claim.
• Fix the Cygan et al. year to 2016 (SIAM J. Comput.) or 2013 (SODA).
• Add an explicit Expected Outcome section with the valid solution clearly stated.

[isPANN]

Renamed from CoveringByCliques to MinimumCoveringByCliques. Converted from decision framing (with bound K) to optimization framing: the objective now minimizes the number of cliques needed to cover all edges. Removed the num_cliques field from the schema. Removed PoorWritten label.

[isPANN]

Fix-issue changelog

• Associated rules: Linked [Rule] PARTITION INTO CLIQUES to MinimumCoveringByCliques #889 and [Rule] COVERING BY CLIQUES to MinimumIntersectionGraphBasis #848.
• Complexity: Fixed Cygan et al. year (2015→2016). Added concrete expression "num_edges^num_edges".
• Schema notes: Added Value = Min<usize> and getter methods.
• ILP: Added companion rule note.
• Example: Added optimality verification (no 3-cover exists). Added Python validation script.

Applied by /fix-issue.