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