[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}
}