[Model] KClique

[isPANN]

Motivation

CLIQUE (GT19) from Garey & Johnson, one of Karp's 21 NP-complete problems (1972). The decision version asks whether a graph contains a clique of size at least k. This is the satisfaction counterpart to MaximumClique (which optimizes clique weight). A dedicated KClique model is needed because several reductions from and to CLIQUE are inherently decision-to-decision mappings that depend on the clique size parameter k — these cannot be expressed as ReduceTo implementations on the optimization MaximumClique.

Blocked rule issues: #229 (3SAT → KClique), #231 (KClique → BalancedCompleteBipartiteSubgraph), #201 (Clique → SubgraphIsomorphism), #206 (Clique → MinimumTardinessSequencing).

Definition

Name: KClique
Reference: Garey & Johnson, Computers and Intractability, A1.2 GT19; Karp (1972)

INSTANCE: Graph G = (V, E), positive integer k ≤ |V|.
QUESTION: Does G contain a clique of size k or more, i.e., a subset V' ⊆ V with |V'| ≥ k such that every two vertices in V' are joined by an edge in E?

Variables

• Count: n = |V| (one variable per vertex)
• Per-variable domain: binary {0, 1} — whether the vertex is in the clique
• Dims: [2; n] — n binary variables, one per vertex
• Meaning: x_v = 1 if vertex v is selected for the clique. The configuration is satisfying if {v : x_v = 1} is a clique (all pairs adjacent) and |{v : x_v = 1}| ≥ k.

Schema (data type)

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

Field	Type	Description
graph	G	The input graph G = (V, E)
k	usize	Minimum clique size threshold

Size fields: num_vertices = |V|, num_edges = |E|, k = clique size threshold.

Complexity

• Best known exact algorithm: O*(1.1996^n) — Xiao & Nagamochi (2017), "Exact Algorithms for Maximum Independent Set," Information and Computation 255:126–146. The algorithm solves maximum independent set; clique is equivalent via complement graph.
• Special cases: Polynomial for chordal graphs (Gavril, 1972), comparability graphs, and graphs with bounded degree.

Extra Remark

• Canonical name: Clique (also: k-Clique, Decision Clique)
• NP-complete (Karp, 1972; transformation from 3-SAT via vertex cover).

Reduction Rule Crossref

• [Rule] 3SAT to KClique #229 (3SAT → KClique)
• [Rule] KClique to BalancedCompleteBipartiteSubgraph #231 (KClique → BalancedCompleteBipartiteSubgraph)
• [Rule] KCLIQUE to SUBGRAPH ISOMORPHISM #201 (KClique → SubgraphIsomorphism)
• [Rule] Clique to Minimum Tardiness Sequencing #206 (KClique → MinimumTardinessSequencing)

How to solve

• It can be solved by (existing) brute force. (Enumerate all 2^n vertex subsets, check if each forms a clique of size ≥ k.)
• It can be solved by reducing to ILP.
• Other: solve MaximumClique on the same graph and compare the result to k.

Example Instance

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

• Edges: {0,1}, {0,2}, {1,3}, {2,3}, {2,4}, {3,4}
• k = 3

(Same graph as the MaximumClique canonical example.)

Expected Outcome

Satisfying solution: config = [0, 0, 1, 1, 1] — selects vertices {2, 3, 4}.

• Pairwise adjacency: {2,3} ✓, {2,4} ✓, {3,4} ✓ — all edges exist.
• Size: 3 ≥ k = 3 ✓.
• This is the unique satisfying configuration (no other subset of size ≥ 3 forms a clique).

BibTeX

@article{XiaoNagamochi2017,
  author    = {Mingyu Xiao and Hiroshi Nagamochi},
  title     = {Exact Algorithms for Maximum Independent Set},
  journal   = {Information and Computation},
  volume    = {255},
  pages     = {126--146},
  year      = {2017},
  doi       = {10.1016/j.ic.2017.06.001}
}

@inproceedings{Karp1972,
  author    = {Richard M. Karp},
  title     = {Reducibility among Combinatorial Problems},
  booktitle = {Complexity of Computer Computations},
  pages     = {85--103},
  year      = {1972},
  publisher = {Plenum Press},
  doi       = {10.1007/978-1-4684-2001-2_9}
}

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	Pass	New problem; unblocks 4 rule issues (#229, #231, #201, #206)
Non-trivial	Pass	Genuinely distinct from MaximumClique (satisfaction vs optimization, k parameter)
Correctness	Pass	Citations verified; complexity 1.1996^n matches Xiao & Nagamochi 2017
Well-written	Warn	Example search space (2^5 = 32) below recommended 128–10,000 range

Overall: 4 passed, 0 failed, 1 warning

---

Usefulness

• KClique does not exist in the codebase (confirmed via pred show KClique).
• The issue identifies 4 concrete blocked rule issues: [Rule] 3SAT to KClique #229 (3SAT → KClique), [Rule] KClique to BalancedCompleteBipartiteSubgraph #231 (KClique → BalancedCompleteBipartiteSubgraph), [Rule] KCLIQUE to SUBGRAPH ISOMORPHISM #201 (KClique → SubgraphIsomorphism), [Rule] Clique to Minimum Tardiness Sequencing #206 (KClique → MinimumTardinessSequencing). All 4 are open, and all target/source problems exist in the codebase.
• Motivation is clear and well-argued: decision-to-decision reductions (e.g., Karp's 3SAT → Clique) require the k parameter and cannot be naturally expressed on the optimization MaximumClique.

Non-trivial

• KClique implements SatisfactionProblem (Metric = bool) while MaximumClique implements OptimizationProblem (Metric = SolutionSize). These are different trait hierarchies.
• KClique adds a k parameter not present in MaximumClique, and the feasibility condition (|V'| ≥ k) is structurally different from weight maximization.
• Cannot be handled as a graph/weight variant of MaximumClique — different trait, different fields, different semantics.
• Karp's classic 3SAT → Clique reduction inherently sets k as a function of the formula, confirming the need for a dedicated decision model.

Correctness

• Karp 1972 — in bibliography as karp1972; title, venue, and pages match.
• Xiao & Nagamochi 2017 — in bibliography as xiao2017; title "Exact Algorithms for Maximum Independent Set", Information and Computation 255:126–146 matches. The 1.1996^n bound is correct and consistent with MaximumClique and MaximumIndependentSet in the codebase.
• Garey & Johnson GT19 — the decision version of CLIQUE is indeed GT19 in G&J Appendix A. Consistent with references.md which lists Clique as a Karp problem (Coding Rules - For AI agents to follow #3).
• Gavril 1972 (chordal graphs) — well-known result, not in the project bibliography. See recommendation below.
• Example verification: Python brute-force confirms {2,3,4} is the unique clique of size ≥ 3. All three edges (2,3), (2,4), (3,4) exist. 11 suboptimal feasible solutions (5 single-vertex + 6 two-vertex cliques).

Well-written

Sections: All 13 required sections present and substantive ✓

Definition completeness: Input structure specified, feasibility as explicit math condition with quantifiers ("every two vertices in V' are joined by an edge in E"), objective clear (|V'| ≥ k). ✓

Symbol consistency: All symbols defined before use (G, V, E, k, x_v, V'). Consistent across sections. ✓

Naming: No Maximum/Minimum prefix needed — this is a satisfaction problem, not optimization. ✓

Example concern: The search space is 2^5 = 32 configurations, below the recommended 128–10,000 range. While the example is fully worked and correct, a slightly larger graph (7–8 vertices, ~128–256 configs) would be more robust for testing.

Recommendations

• Increase example size to 7–8 vertices for a search space in the 128–256 range. This also allows for multiple satisfying solutions to better exercise the satisfaction semantics.
• Add Gavril 1972 to the BibTeX section for the chordal graph polynomial-time claim.
• Consider mentioning in "How to solve" that solving MaximumClique on the same graph and comparing the result to k is an alternative solver strategy.

[isPANN]

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

• Paper (PDF): check definition, proof sketch, and example figure
• CLI demo (build from source: cargo install --path problemreductions-cli):

  pred show KClique
  pred create --example KClique -o instance.json
  pred solve instance.json KClique --solver brute-force

• 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.