[Rule] MaximumCoKPlex to ILP

[zhangjieqingithub]

Source

MaximumCoKPlex

Target

ILP

Motivation

This rule connects MaximumCoKPlex to an existing solver hub immediately. The formulation is linear, compact, and natural: one binary variable per source vertex and one degree-cap constraint per source vertex.

Reference

• Maritza Hernandez, Arman Zaribafiyan, Maliheh Aramon, Mohammad Naghibi, "A Novel Graph-based Approach for Determining Molecular Similarity," arXiv:1601.06693, 2016. https://arxiv.org/abs/1601.06693
• Balabhaskar Balasundaram, Sergiy Butenko, Illya V. Hicks, "Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem," Operations Research 59(1):133-142, 2011. https://doi.org/10.1287/opre.1100.0851

The concrete MaximumCoKPlex -> ILP<bool> construction below is a direct inference from the co-k-plex definition and the standard integer-programming pattern for clique relaxations.

Reduction Algorithm

Let the source instance be a weighted graph (G=(V,E)), with (n=|V|), weights (w_v), and parameter (k\ge 1).

Create a binary ILP with one variable (x_v \in {0,1}) for each vertex (v \in V), where (x_v=1) means that (v) is selected.

Set the objective to
[
\max \sum_{v\in V} w_v x_v.
]

For each vertex (v), let (N(v)) be its neighborhood in (G) and (d(v)=|N(v)|). Add the linear constraint
[
\sum_{u\in N(v)} x_u \le (k-1) + d(v)(1-x_v).
]

Equivalently,
[
\sum_{u\in N(v)} x_u + d(v)x_v \le d(v)+k-1.
]

Correctness intuition:

• If (x_v=1), the constraint becomes (\sum_{u\in N(v)} x_u \le k-1), so (v) has at most (k-1) selected neighbors.
• If (x_v=0), the right-hand side is (d(v)+k-1), so the constraint is automatically satisfied.

Thus feasible ILP solutions are exactly feasible co-k-plex selections, and the objective is preserved.

Size Overhead

Target metric	Formula (using symbols above)
num_vars	(n =
num_constraints	(n =

Validation Method

• Closed-loop tests on small graphs: brute-force the source problem and compare with the ILP optimum.
• Regression at (k=1): verify that the source model agrees with MaximumIndependentSet, and that the ILP optimum matches the known MIS optimum on the same weighted graphs.
• Feasibility cross-check: for every extracted ILP solution (x), verify directly in the source model that every selected vertex has induced degree at most (k-1).

Example

1. Source instance: (C_5) with
   [
   E={(0,1),(1,2),(2,3),(3,4),(4,0)},
   ]
   weights (w=(5,1,4,1,3)), and (k=2).

2. Construction: Introduce binary variables (x_0,\dots,x_4). The objective is
   [
   \max 5x_0 + x_1 + 4x_2 + x_3 + 3x_4.
   ]

   Since every vertex has degree (2), each constraint has the form
   [
   \sum_{u\in N(v)} x_u + 2x_v \le 3.
   ]

   Therefore the ILP constraints are
   [
   x_1 + x_4 + 2x_0 \le 3,
   ]
   [
   x_0 + x_2 + 2x_1 \le 3,
   ]
   [
   x_1 + x_3 + 2x_2 \le 3,
   ]
   [
   x_2 + x_4 + 2x_3 \le 3,
   ]
   [
   x_3 + x_0 + 2x_4 \le 3.
   ]

3. Target instance: a binary ILP with 5 variables, 5 constraints, and the objective above. The optimal ILP solution is (x=(1,0,1,0,1)), which maps identically back to the source solution (S={0,2,4}) of value (12).

BibTeX

@article{Hernandez2016MolecularSimilarity,
  title={A Novel Graph-based Approach for Determining Molecular Similarity},
  author={Hernandez, Maritza and Zaribafiyan, Arman and Aramon, Maliheh and Naghibi, Mohammad},
  journal={arXiv preprint arXiv:1601.06693},
  year={2016},
  url={https://arxiv.org/abs/1601.06693}
}

@article{BalasundaramButenkoHicks2011KPlex,
  title={Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem},
  author={Balasundaram, Balabhaskar and Butenko, Sergiy and Hicks, Illya V.},
  journal={Operations Research},
  volume={59},
  number={1},
  pages={133--142},
  year={2011},
  doi={10.1287/opre.1100.0851},
  url={https://doi.org/10.1287/opre.1100.0851}
}

[isPANN]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	Pass	No existing direct MaximumCoKPlex -> ILP path; companion model #1015 explicitly relies on this rule for ILP solving.
Non-trivial	Pass	Constructs n linear "big-M" constraints with d(v)*x_v coupling; not a 1-to-1 relabeling.
Correctness	Pass	Both cited papers (Hernandez 2016 arXiv:1601.06693, Balasundaram-Butenko-Hicks 2011 Operations Research) exist; the construction is a direct adaptation of the standard k-plex ILP template to the co-k-plex (induced max degree <= k-1) formulation. Hand-verified equivalence on the C_5 example and corner cases.
Completeness	Pass	Construction works for every MaximumCoKPlex instance the model exposes; traced on multiple corner cases (see below).
Well-written	Pass	All template sections present and substantive; size-overhead fields num_vars, num_constraints match pred show ILP schema (size_fields: ['num_constraints', 'num_variables', 'num_vars']); symbols n, V, E, w_v, k, d(v), N(v) all defined before use.

Overall: 5 passed, 0 failed, 0 warnings

---

Usefulness

pred path MaximumCoKPlex ILP is currently undefined (source unknown to the registry — model #1015 is still being implemented). The companion model issue #1015 advertises ILP as a planned solver path via this rule. No competing reduction exists.

Non-trivial

The reduction adds n linear constraints of the form
sum_{u in N(v)} x_u + d(v) * x_v <= d(v) + k - 1
which actively couples each vertex with its neighborhood through a big-M-style switch (d(v)*(1-x_v)). This is genuine structural transformation, not a variable relabel or subtype coercion.

Correctness

• Hernandez et al. 2016 (arXiv:1601.06693) — already in docs/paper/references.bib as Hernandez2016MolecularSimilarity. The paper introduces a co-k-plex / k-defective-clique formulation in the context of molecular similarity matching on quantum annealers. Verified.
• Balasundaram, Butenko, Hicks 2011 (Operations Research 59(1)) — DOI 10.1287/opre.1100.0851, "Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem". This is the canonical reference for the k-plex ILP template. The same big-M pattern (with non-neighbors on the complement side) is used for the standard k-plex; the issue correctly adapts it to co-k-plex by working on the original graph with neighbors.
• Equivalence verified by exhaustive enumeration on the C_5 example: source feasibility (induced max degree <= 1) and the ILP constraint produce the same feasible set, and the optimum is 12 at x=(1,0,1,0,1) as stated.

Completeness

Literature. Both references state the construction is parameterized by an arbitrary graph G and parameter k >= 1, with no preconditions on connectivity, density, or weight sign. The big-M structure of the constraint ensures it is vacuously satisfied when x_v=0 and reduces to the degree cap when x_v=1, for every vertex independently.

Corner cases hand-traced against the algorithm:

1. Empty graph (n=3, no edges, k=2). All d(v)=0, N(v)=empty. Constraint becomes 0 + 0*x_v <= 0 + 1, always satisfied. Source: induced degree is always 0, so all subsets are feasible. Both agree on all 8 configs.
2. Triangle K_3, k=2. All d(v)=2. Constraint: sum_{u != v} x_u + 2 x_v <= 3. For x=(1,1,1): lhs=2+2=4 > 3, infeasible — matches source (induced K_3 has each vertex of degree 2 > k-1=1). All 7 other configs match.
3. Single isolated vertex, k=1 (MIS reduction). d(0)=0, constraint 0 + 0 <= 0, trivially satisfied. Source allows x=(1). Matches.
4. K_2, k=1 (MIS). d(v)=1, constraint x_other + x_v <= 1. Correctly forbids x=(1,1); accepts (0,0),(0,1),(1,0). Matches source MIS feasibility exactly.

No corner case breaks the construction. The reduction works on disconnected graphs, isolated vertices, empty edge sets, and the degenerate k=1 case (which collapses to the standard MIS LP).

Codebase corner cases. pred show MaximumIndependentSet (the k=1 specialization) and pred show ILP confirm the relevant size fields. Schema for MaximumCoKPlex from #1015 supports SimpleGraph, weights One/i32, and bound_k: usize; the algorithm uses only N(v), d(v), w_v, and k, all of which are well-defined on those variants.

Well-written

• All 8 template sections (Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, Example) are present and substantive.
• Algorithm is fully specified: variables, objective, and constraints written as closed-form formulas with both expanded and simplified forms.
• Symbols G, V, E, n, w_v, k, x_v, N(v), d(v) are all defined before use.
• Size-overhead fields num_vars and num_constraints match the ILP schema getters reported by pred show ILP --json (size_fields: ['num_constraints', 'num_variables', 'num_vars']).
• Example is non-trivial (C_5 with mixed weights, k=2), exercises the core degree-cap structure, has multiple suboptimal feasible solutions (e.g., {0}=5, {0,2}=9, {0,3}=6, {0,2,4}=12), and is round-trip testable. The expected optimum and witness are provided.
• Solution extraction is implicit and correct: identity mapping x_v <-> selection of v.

[isPANN]

auto-pipeline: implementation landed on batch-add-models as commit b4e6caa.