[Model] MaximumEdgeWeightedKClique

[zhangjieqingithub]

Motivation

The repository already has:

• MaximumClique: optimize over cliques using vertex weights
• KClique: the decision problem asking whether a clique of size at least k exists

What is missing is the fixed-cardinality edge-weighted optimization variant: choose exactly k vertices that form a clique and maximize the total weight of the induced clique edges. This is the natural exact-k specialization of the edge-weighted maximal clique literature.

Associated rule:

• [Rule] MaximumEdgeWeightedKClique to ILP #1021: MaximumEdgeWeightedKClique -> ILP

Definition

Name: MaximumEdgeWeightedKClique
Reference:

• L. Gouveia, P. Martins, "Solving the maximum edge-weight clique problem in sparse graphs with compact formulations," EURO Journal on Computational Optimization 3(1):1-30, 2015. https://doi.org/10.1007/s13675-014-0028-1
• M. Hunting, U. Faigle, W. Kern, "A Lagrangian relaxation approach to the edge-weighted clique problem," European Journal of Operational Research 131(1):119-131, 2001. https://doi.org/10.1016/S0377-2217(99)00449-X

Given a simple undirected graph G = (V, E), an edge-weight function w : E -> R, and an integer k with 0 <= k <= |V|, find a subset S subseteq V such that:

• |S| = k
• every two distinct vertices in S are adjacent in G

and maximizing
sum_{ {u,v} subseteq S, {u,v} in E } w_uv.

Equivalently, the objective is the total weight of the edges induced by the selected k-clique.

Important modeling choices for this proposal:

• the graph is simple and undirected
• edge weights may be positive, zero, or negative
• cliques of size 0 and 1 are allowed when k takes those values, with objective value 0
• there is no separate vertex-weight term

Variables

• Count: |V| binary variables, one per vertex
• Per-variable domain: {0,1}
• Meaning: x_v = 1 iff vertex v is selected into the clique

A configuration is feasible iff the selected vertices form a clique of size exactly k.

Schema (data type)

Type name: MaximumEdgeWeightedKClique
Variants: edge-weight type only

Field	Type	Description
graph	SimpleGraph	The input graph G = (V, E)
edge_weights	Vec<W>	Edge weights in the graph's edge order
k	usize	Required clique size

Recommended concrete variants:

• (SimpleGraph, i32) default
• (SimpleGraph, f64)

Complexity

A conservative exact baseline is to enumerate all k-vertex subsets and test whether each induces a clique.

This gives
O(binomial(num_vertices, k) * k^2)

and therefore a conservative worst-case registry complexity of
2^num_vertices.

I have not verified a sharper exact worst-case bound specifically for the exact-k edge-weighted specialization, so the proposal should use the conservative 2^num_vertices complexity string.

References for the surrounding MEWC family:

• https://doi.org/10.1007/s13675-014-0028-1
• https://doi.org/10.1016/S0377-2217(99)00449-X

Extra Remark

This is the exact-cardinality edge-weighted clique model. It is distinct from:

• MaximumClique, which uses vertex weights and does not enforce exact cardinality
• KClique, which is a decision problem with threshold semantics |S| >= k

The literature often studies a bounded-cardinality edge-weighted clique model with |S| <= b; this proposal is the exact-k specialization.

Reduction Rule Crossref

• [Rule] MaximumEdgeWeightedKClique to ILP #1021

How to solve

• It can be solved by brute force.
• It can be solved by reducing to ILP via [Rule] MaximumEdgeWeightedKClique to ILP #1021 ([Rule] MaximumEdgeWeightedKClique to ILP).
• Other, refer to ...

Example Instance

Let

• V = {0,1,2,3}
• E = {{0,1}, {0,2}, {1,2}, {0,3}, {1,3}}
• w_01 = 5
• w_02 = 4
• w_12 = -1
• w_03 = 1
• w_13 = 0
• k = 3

So the graph contains the triangles {0,1,2} and {0,1,3}, but not {0,2,3} or {1,2,3} because edge {2,3} is missing.

Expected Outcome

The feasible 3-cliques are:

• {0,1,2} with objective value 5 + 4 - 1 = 8
• {0,1,3} with objective value 5 + 1 + 0 = 6

Thus an optimal configuration is
x = (1,1,1,0)

corresponding to clique {0,1,2}, with optimal value 8.

This example is intentionally nontrivial:

• the better clique contains a negative edge
• some 3-vertex subsets are infeasible because they are not cliques

BibTeX

@article{GouveiaMartins2015MEWC,
  author  = {Luis Gouveia and Paulo Martins},
  title   = {Solving the maximum edge-weight clique problem in sparse graphs with compact formulations},
  journal = {EURO Journal on Computational Optimization},
  volume  = {3},
  number  = {1},
  pages   = {1--30},
  year    = {2015},
  doi     = {10.1007/s13675-014-0028-1},
  url     = {https://doi.org/10.1007/s13675-014-0028-1}
}

@article{HuntingFaigleKern2001,
  author  = {Marcel Hunting and Ulrich Faigle and Walter Kern},
  title   = {A Lagrangian relaxation approach to the edge-weighted clique problem},
  journal = {European Journal of Operational Research},
  volume  = {131},
  number  = {1},
  pages   = {119--131},
  year    = {2001},
  doi     = {10.1016/S0377-2217(99)00449-X},
  url     = {https://doi.org/10.1016/S0377-2217(99)00449-X}
}

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	Pass	Novel problem not in registry; concrete companion rule #1021 planned (MaximumEdgeWeightedKClique to ILP)
Non-trivial	Pass	Edge-weighted, exact-cardinality objective — distinct from vertex-weighted MaximumClique and from the decision KClique (`
Correctness	Pass	Both cited references verified; definition is mathematically well-formed; conservative 2^num_vertices complexity acknowledged as a baseline
Well-written	Pass	All template sections present and substantive; worked example exercises core structure (forces choice between a higher-weight clique with a negative edge and a lower-weight alternative)

Overall: 4 passed, 0 warnings, 0 failed

---

Usefulness

• pred show MaximumEdgeWeightedKClique returns "Unknown problem" — the model does not yet exist in the registry.
• Distinct from existing MaximumClique (vertex-weighted, no cardinality constraint) and KClique (decision problem, |S| >= k threshold).
• Companion rule [Rule] MaximumEdgeWeightedKClique to ILP #1021 ([Rule] MaximumEdgeWeightedKClique to ILP) is explicitly linked under "Reduction Rule Crossref" and "How to solve", satisfying the orphan-node check and the ILP-claim requirement.
• Motivation is concrete: fixed-cardinality edge-weighted clique is a well-studied specialization of the MEWC family (cited literature).

Non-trivial

• Feasibility constraint (induced clique on exactly k vertices) plus an objective summing edge weights (not vertex weights) gives a genuinely different combinatorial structure from anything currently in the catalog.
• Allowing negative edge weights and enforcing exactly k selected vertices yields a constrained quadratic-style objective that is not a trivial relabeling of MaximumClique or KClique.

Correctness

• Definition: Clean mathematical statement with explicit input (G, w, k), feasibility (|S| = k and S is a clique), and objective (sum of induced-edge weights). Modeling choices (simple/undirected, real-valued weights including negatives, edge-only objective, sizes 0/1 valid with value 0) are stated explicitly.
• Schema: Edge weights stored as Vec<W> in graph edge order is consistent with how the codebase already stores edge data (e.g., MEWC literature universally uses edge-indexed weight vectors). k: usize matches the existing KClique convention.
• Representation feasibility: Proposed i32 / f64 weights cover the stated real-valued domain (including negatives).
• Complexity claim: 2^num_vertices is a deliberately conservative upper bound. The issue is transparent that no sharper exact-k MEWC bound was verified, and O(C(n,k) * k^2) brute-force enumeration is correctly upper-bounded by 2^n * poly. Consistent with conservative baselines already used in the registry (e.g., KClique itself).
• References (external verification):
  • Gouveia & Martins, Solving the maximum edge-weight clique problem in sparse graphs with compact formulations, EURO J. Comput. Optim. 3(1):1–30, 2015 (DOI 10.1007/s13675-014-0028-1) — confirmed via Semantic Scholar + dblp. Real paper, authors and venue match, topic is the MEWC family.
  • Hunting, Faigle, Kern, A Lagrangian relaxation approach to the edge-weighted clique problem, EJOR 131(1):119–131, 2001 (DOI 10.1016/S0377-2217(99)00449-X) — confirmed via RePEc. Real paper, authors/venue/year match, addresses edge-weighted clique via Lagrangian relaxation.
• Neither reference is currently in docs/paper/references.bib; both are appropriate primary sources for the MEWC family.

Well-written

• All required template sections are present (Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, Example Instance, Expected Outcome, BibTeX).
• Symbols (G = (V, E), w, k, S, x_v) are defined before use and consistent across sections.
• Naming follows the Maximum... convention for an optimization problem.
• Example instance has 4 vertices / 5 edges / k = 3, two feasible 3-cliques with distinct objective values (8 and 6) and two infeasible 3-subsets — exercises both the clique constraint and the negative-edge sensitivity of the edge-weighted objective. Provides a clean round-trip test target. Tiny enough for brute-force verification (config space 2^4 = 16).

Recommendations

• Optional: when the model is added, also cite the Hosseinian, Butenko et al. surveys ("The Maximum Edge Weight Clique Problem: Formulations and Solution Approaches", 2017) and Park, Lee, Park (1996) for additional formulation context — already cited in companion rule [Rule] MaximumEdgeWeightedKClique to ILP #1021.
• Optional follow-up rule worth considering after [Rule] MaximumEdgeWeightedKClique to ILP #1021 lands: MaximumEdgeWeightedKClique -> QUBO via the standard quadratic edge-product encoding (matches the nonconvex quadratic formulation in Hosseinian et al. 2018).

[isPANN]

/review-structural — commit feb9a6e (post-impl, code-quality + bug sweep)

Verdict: pass — model implementation is correct, schema/paper/tests/CLI hookups are all in place and match the issue definition.

Issue compliance

• Mathematical definition matches issue: yes — maximize Σ_{ {u,v} ⊆ S, {u,v} ∈ E } w_uv over |S|=k cliques, k∈[0, |V|], weights real-valued, k=0/k=1 admitted with objective 0, fixed SimpleGraph.
• Schema fields match: yes — graph: SimpleGraph, edge_weights: Vec<W>, k: usize exactly match the issue's schema table; the dimension list only includes weight (graph fixed to SimpleGraph in the type), (SimpleGraph, i32) is default and (SimpleGraph, f64) is the alternate variant as proposed.
• Canonical example: ok — registered via canonical_model_example_specs() with the issue's 4-vertex instance (edges (0,1),(0,2),(1,2),(0,3),(1,3), weights [5,4,-1,1,0], k=3), optimal config [1,1,1,0], optimal value 8. The paper figure uses the same instance via load-model-example.

Structural checklist (model)

All 16 items pass:

1. src/models/graph/maximum_edge_weighted_k_clique.rs exists.
   2-3. Two inventory::submit! blocks (ProblemSchemaEntry, ProblemSizeFieldEntry), struct derives Serialize/Deserialize/Clone/Debug.
   4-5. impl Problem for MaximumEdgeWeightedKClique<W> with Value = Max<W::Sum>.
   6-8. #[cfg(test)] #[path = ...] test link; test file present with 12 fn test_* functions (≥3).
   9-10. Registered in src/models/graph/mod.rs (pub(crate) mod, pub use, and added to canonical_model_example_specs collector).
2. declare_variants! with default <i32> plus <f64>, both at complexity "2^num_vertices" (matches issue's conservative bound).
   12-13. CLI: no alias needed; schema-driven create handles --graph, --edge-weights, --k automatically (all three present in flag_map() in cli.rs lines 995, 997, 1019; schema_driven_supported_problem returns true for everything except ILP/CircuitSAT; resolve_schema_field_type already handles Vec<W>).
3. Canonical model example registered via canonical_model_example_specs() and collected in graph/mod.rs.
   15-16. Paper: display-name entry ("MaximumEdgeWeightedKClique": [Maximum Edge-Weighted $k$-Clique]) and problem-def block with worked example highlighting the negative-edge subtlety, plus CeTZ figure and pred-commands block.

No blacklisted auto-generated files in the diff.

Semantic review

• evaluate() correctness: rejects infeasible configs (is_k_clique_config returns false when |selected| ≠ k or any selected pair is non-adjacent), returning Max(None); for feasible configs sums weights of edges where both endpoints have config[u]==1 && config[v]==1. Matches the issue's induced-edge objective exactly. k=0 → empty selection → sum is W::Sum::zero(), so Max(Some(0)) — matches issue's convention.
• dims() returns vec![2; num_vertices] — correct binary domain.
• Size getter consistency: num_vertices(), num_edges() are the inherent getter names declared in ProblemSizeFieldEntry, matching the complexity expression "2^num_vertices".
• Weights via inherent methods (edge_weights() -> &[W]), no weight trait abuse.
• Constructor guards: panics on edge_weights.len() != graph.num_edges() and on k > num_vertices(), with regression tests for both.
• Tests verify the canonical optimum (config [1,1,1,0] → 8), the secondary triangle (config [1,1,0,1] → 6), wrong-size infeasibility (|S|=0,2,4 → None when k=3), not-a-clique infeasibility ({0,2,3} and {1,2,3}), brute-force solver witness recovery, the k=0/k=1 edge cases (both 0), f64 variant, serde round-trip, and NAME/variant() registration.

Findings

• Blockers (correctness): none.
• Nits (quality/HCI):
  • is_k_clique_config treats any config[i] value other than 1 as "not selected" rather than rejecting non-binary inputs. Since dims() constrains the search space to {0,1}^n, the solver never produces such configs in practice, but is_valid_solution/evaluate are public and a non-binary input would silently degrade rather than panic or return Max(None). Consider either documenting "values not in {0,1} are treated as 0" or rejecting them explicitly.
  • Schema field description for edge_weights says "Edge weights in graph edge order" — fine, but per the project convention noted in feedback_getter_description.md the description could just say "edge_weights" if a fully self-documenting name is preferred. Optional.
  • The companion rule MaximumEdgeWeightedKClique -> ILP from [Rule] MaximumEdgeWeightedKClique to ILP #1021 was deliberately scoped out of this commit; the paper does already render its reduction-rule entry (line 13482), which is fine because the rule was merged separately before paper rebuild.