[Model] MaximumCoKPlex

[zhangjieqingithub]

Motivation

Co-k-plex is a standard clique-relaxation / near-independent-set model: it generalizes MaximumIndependentSet, captures controlled conflicts inside the chosen vertex set, and has a clean ILP formulation that would connect it immediately to the main solver graph.

Definition

Name: MaximumCoKPlex
Reference: https://arxiv.org/abs/1601.06693 ; https://doi.org/10.1016/j.dam.2021.10.015

Given an undirected graph (G=(V,E)), vertex weights (w:V\to \mathbb{R}), and an integer (k \ge 1), find a subset (S \subseteq V) maximizing (\sum_{v\in S} w_v) such that every vertex has induced degree at most (k-1) inside (S), i.e.
[
\deg_{G[S]}(v) \le k-1 \quad \text{for all } v \in S.
]

Equivalently, (S) induces a subgraph of maximum degree at most (k-1).

Variables

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

Schema (data type)

Type name: MaximumCoKPlex
Variants: graph topology (SimpleGraph initially), weight type (One, i32), and (k)-parameter (KN default, with fixed variants such as K1, K2, K3, ... supported later)

Field	Type	Description
graph	G	the input graph (G=(V,E))
weights	Vec	vertex weights (w_v)
bound_k	usize	the co-k-plex parameter (k\ge 1); for fixed-(K) variants this equals the type-level value

Complexity

• Best known exact algorithm: conservative baseline for the default KN variant: exhaustive subset enumeration in (O(2^n(n+m))), so the initial registry complexity string should be 2^num_vertices
• References: https://arxiv.org/abs/1601.06693 ; https://doi.org/10.1016/j.dam.2021.10.015

Extra Remark

MaximumCoKPlex is exactly MaximumIndependentSet when (k=1). It is also equivalent to the maximum ((k-1))-dependent-set problem, and on the complement graph it corresponds to the maximum (k)-plex viewpoint used in the clique-relaxation literature.

Reduction Rule Crossref

• [Rule] MaximumCoKPlex to ILP #1016

How to solve

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

Example Instance

Take the 5-cycle (C_5) with
[
V={0,1,2,3,4},\quad
E={(0,1),(1,2),(2,3),(3,4),(4,0)},
]
weights
[
w=(5,1,4,1,3),
]
and (k=2).

So we seek a maximum-weight vertex set whose induced subgraph has maximum degree at most (1).

Expected Outcome

One optimal configuration is
[
x=(1,0,1,0,1),
]
corresponding to (S={0,2,4}).

The induced subgraph (G[S]) contains only the edge ((4,0)), so the selected-vertex degrees are ((1,0,1)), all at most (k-1=1). Its objective value is
[
w(S)=5+4+3=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{HosseinianButenko2022KDependent,
  title={An improved approximation for Maximum k-dependent Set on bipartite graphs},
  author={Hosseinian, Seyedmohammadhossein and Butenko, Sergiy},
  journal={Discrete Applied Mathematics},
  volume={307},
  pages={95--101},
  year={2022},
  doi={10.1016/j.dam.2021.10.015},
  url={https://doi.org/10.1016/j.dam.2021.10.015}
}

[isPANN]

Issue Quality Check — Model

Check	Result	Details
Usefulness	Pass	Novel problem not yet in pred list; companion [Rule] MaximumCoKPlex to ILP issue #1016 is linked under "Reduction Rule Crossref"
Non-trivial	Pass	Genuinely new feasibility constraint (induced-degree bound), distinct from existing models (MIS, MaximumClique, MaximalIS, KColoring, etc.)
Correctness	Pass (with recommendation)	Both cited papers verified to exist and to discuss the maximum weighted co-k-plex / k-dependent set; complexity claim is intentionally conservative
Well-written	Pass	All template sections present and substantive; example computed and verified

Overall: 4 passed, 0 failed, 0 warnings

---

Usefulness

• pred show MaximumCoKPlex, pred show CoKPlex, pred show MaximumKPlex all return "Unknown problem" — the model does not exist yet.
• MaximumCoKPlex reduces to MaximumIndependentSet when k=1, and the issue explicitly plans a direct ILP reduction via companion issue [Rule] MaximumCoKPlex to ILP #1016, which is already filed and links back to this issue. The "How to solve" section checks both brute-force and ILP-via-[Rule] MaximumCoKPlex to ILP #1016, so the ILP-claim ⇒ companion-issue requirement is satisfied.
• Motivation is concrete: clique-relaxation / near-independent-set model with quantum-annealing applications (cf. Hernandez et al. 2016 use the co-k-plex relaxation for molecular similarity).

Non-trivial

• The feasibility constraint "every selected vertex has induced degree at most k-1" is genuinely distinct from the constraints of every existing model in pred list (MIS requires degree 0, MaximumClique requires degree |S|−1, KColoring is partition-based, etc.).
• For k=1, this specializes to MIS — but for general k it is a strictly richer family of optimization problems, not a trivial repackaging or variant.

Correctness

Project bibliography (docs/paper/references.bib): neither cited reference is yet in the bib file — verified via external sources below.

External verification:

1. Hernandez, Zaribafiyan, Aramon, Naghibi — arXiv:1601.06693 (2016) — Verified at https://arxiv.org/abs/1601.06693. Title "A Novel Graph-based Approach for Determining Molecular Similarity" is correct. The abstract explicitly says: "we relax the definition of similarity using the maximum weighted co-k-plex relaxation method, which allows dissimilarities among graphs up to a predetermined level." So the paper genuinely introduces / uses the maximum weighted co-k-plex problem the issue claims it does.

2. Hosseinian & Butenko — Discrete Applied Mathematics 307:95–101 (2022), DOI 10.1016/j.dam.2021.10.015 — Verified. Title "An improved approximation for Maximum k-dependent Set on bipartite graphs" matches, the venue (DAM vol. 307, 2022, pp. 95–101) matches, and the paper does establish a (1 + k/(k+2))-approximation in O(kmn) time. Author list matches. (arXiv preprint mirror: arXiv:2202.01004.)

Definitional cross-check. The co-k-plex definition the issue gives ("deg_{G[S]}(v) ≤ k-1 for all v in S") matches the standard textbook definition used in clique-relaxation literature (e.g., Balasundaram–Butenko–Hicks, Operations Research 59(1), 2011; McClosky–Arellano–Hicks, "Co-k-plex vertex partitions"). The "Extra Remark" claim that this is equivalent to maximum (k-1)-dependent set is consistent with the convention k-dependent ⇔ max induced degree ≤ k; the alternative convention k-dependent ⇔ max induced degree ≤ k-1 (e.g., Hosseinian–Butenko) would make co-k-plex equivalent to k-dependent set rather than (k-1)-dependent set. Both conventions exist in the literature, so the remark is defensible but not unambiguous; this is a stylistic note, not an error.

Complexity bound. The registered string is 2^num_vertices and the issue explicitly calls this a "conservative baseline". It is a correct upper bound (exhaustive subset enumeration is always feasible), matches the convention used by sibling models like MaximumClique/MaximumIndependentSet before they were refined, and is appropriate for first registration.

Example verified by Python brute force: for C_5, weights (5,1,4,1,3), k=2, the optimum is S = {0, 2, 4} with value 12; induced degrees are (1, 0, 1), all ≤ k-1 = 1. There are 21 feasible subsets with 12 distinct objective values, so the example supports a meaningful round-trip test (multiple suboptimal feasibles per the 4d rule of thumb).

Recommendations

• Tighter complexity bound available. The maximum k-plex literature (Gao–Chen–Yin–Cai–Yin, "FastBB", and Zhou et al. PVLDB 2022) gives exact algorithms running in O*(γ_k^n) with γ_1 = 1.466, γ_2 = 1.755, γ_3 = 1.889, all strictly less than 2. Since co-k-plex on G corresponds to k-plex on the complement graph, the same bounds transfer. When the model is implemented, consider tightening the KN complexity string from 2^num_vertices to a complement-graph k-plex bound such as 1.889^num_vertices for the small-k cases, citing those papers; not blocking for this issue.
• Add a bib entry for Balasundaram–Butenko–Hicks (2011, Operations Research 59(1):133–142) — this is the canonical reference for the maximum k-plex / co-k-plex framing and would strengthen the "Reference" section. The companion issue [Rule] MaximumCoKPlex to ILP #1016 already cites this paper, so it would be natural to add here too.
• Consider explicitly stating the k=1 collapse in the Definition section as a sanity check ("when k=1, the constraint reduces to deg_{G[S]}(v) ≤ 0, recovering MaximumIndependentSet"), instead of only in "Extra Remark".

Well-written

All template sections are present and substantive:

Section	Status
Motivation	Concrete (clique relaxation, conflict tolerance, ILP connectivity)
Name	MaximumCoKPlex — follows Maximum* naming convention
Reference	Two citations with arXiv ID and DOI, both verified
Definition	Formal, with input, feasibility constraint, and objective separately stated; quantifiers explicit
Variables	Count, domain, and meaning all given
Schema	Type name, variants (SimpleGraph/One/KN default plus future K1..Kj), three-column field table with graph, weights, bound_k (matches the existing bound_k convention used in ConsecutiveSets)
Complexity	Best-known baseline algorithm explicitly described, concrete bound 2^num_vertices in the registry form, references provided
How to solve	Brute-force and ILP (via #1016) both checked; companion direct-ILP rule issue linked as required when ILP is claimed
Example Instance	C_5 with non-trivial weights and k=2
Expected Outcome	Optimal configuration, induced subgraph, per-vertex degree check, and objective value all spelled out
BibTeX	Both entries match the citations

Symbols are consistent across sections (V, E, w, k, n all defined and reused). Schema field names follow established codebase conventions.

[isPANN]

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

Verdict: pass — model implementation matches the issue spec cleanly; only minor HCI/defensive-coding nits.

Issue compliance

• Mathematical definition matches issue: yes — is_co_k_plex_config enforces deg_{G[S]}(v) <= k-1 for every selected vertex via induced-degree counting on the edge list.
• Schema fields match: yes — graph (G), weights (Vec), bound_k (usize) align with the issue's schema table. The MaximumCoKPlex/bound_k -> --k override in help_flag_name cleanly reuses the existing --k clap arg per the project's flag-naming convention.
• Canonical example: ok — 5-cycle, w=(5,1,4,1,3), k=2 -> S={0,2,4}, value=12 matches the issue's expected outcome exactly. Registered via inventory and surfaced in docs/paper/data/examples.json and the paper figure.

Structural completeness (model checklist)

• (1) Model file src/models/graph/maximum_co_k_plex.rs — PASS
• (2) inventory::submit! for ProblemSchemaEntry + ProblemSizeFieldEntry — PASS
• (3) Serialize, Deserialize derives — PASS (with serde bounds for generics + #[serde(skip)] on _phantom)
• (4) Problem impl — PASS
• (5) type Value = Max<W::Sum> — PASS (witness-capable maximum objective)
• (6) #[cfg(test)] #[path = ...] test link — PASS
• (7) Test file exists — PASS
• (8) >= 3 test functions — PASS (8 tests; coverage spans creation, feasible/infeasible evaluate, brute-force solver+witness, k=1 MIS equivalence, serialization roundtrip, NAME+variant, panic on k=0, panic on weight length mismatch)
• (9) pub(crate) mod maximum_co_k_plex in models/graph/mod.rs — PASS
• (10) Re-export pub use maximum_co_k_plex::MaximumCoKPlex — PASS
• (11) declare_variants! with default <SimpleGraph,One,KN> + <SimpleGraph,i32,KN> — PASS
• (12) CLI alias resolve: registry-driven (aliases: &[] is fine; canonical name resolves itself) — PASS
• (13) CLI create support: bound_k -> --k via help_flag_name override; schema_field_flag_keys adds k to the lookup keys; semantics validator enforces k>=1 and matching graph/weights — PASS
• (14) canonical_model_example_specs() registered + threaded through models/graph/mod.rs aggregator — PASS
• (15) display-name entry "MaximumCoKPlex": [Maximum Co-$k$-Plex] — PASS
• (16) problem-def("MaximumCoKPlex") block with C_5 worked example, $k=1$ equivalence note, and pred-commands stanza — PASS

No blacklisted auto-generated files in this commit's diff.

Semantic spot-checks

• evaluate() returns Max(None) on infeasibility before computing the objective — correct for the project's optimization-feasibility convention. Test test_maximum_co_k_plex_evaluate_infeasible exercises both a partial-violation (vertex 1 has induced degree 2) and the all-ones case.
• is_co_k_plex_config early-returns false on bound_k == 0, defensive against a deserialized instance bypassing the constructor (serde default for KN yields bound_k = 0).
• dims() = vec![2; n] — correct binary configuration space.
• Size getters num_vertices(), num_edges() match the ProblemSizeFieldEntry declaration and are consistent for downstream overhead expressions.
• Weights managed via inherent methods (weights(), is_weighted()) — follows project convention.
• Complexity string "2^num_vertices" matches the issue's conservative brute-force baseline and uses only concrete numeric values.

Findings

• Blockers (correctness): none
• Nits (quality/HCI):
  • Serde fallback for the bound_k field on the KN variant uses default_bound_k::<KN>() = 0, which then silently fails every evaluate() (always Max(None)). Not a bug for round-tripped JSON (the field is always serialized), but a malformed input file missing bound_k will be accepted and yield a degenerate problem. Consider validating in a TryFrom/#[serde(deserialize_with = ...)] or in the factory closure surfaced by declare_variants! so the failure is loud at load time rather than silent at evaluate time.
  • is_co_k_plex_config uses config.get(u).copied().unwrap_or(0) for both endpoints. In practice config.len() == graph.num_vertices() (enforced upstream by dims()), so the unwrap_or(0) branch is dead. Mild noise; cleaner would be a slice-index after an explicit length check, or just config[u] and let a debug assert catch the impossible case.
  • The MaximumCoKPlex/i32 usage hint in schema_semantics.rs is good, but the equivalent KN/One unit-weight path isn't surfaced; a unit-weight new-user might try pred create MaximumCoKPlex --graph ... --k 2 without --weights and hit the generic schema error. Worth a sentence in the unit-weight derivation path if it doesn't already exist.