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