How to formulate a maximum size k-plex problem in integer linear programming? First, k-plex is a subgraph that each vertex is connected to at least n-k vertices, where n is the size of subgraph. I found some materials that similar to k-plex : page 5 of This gave a formulation of k-clique(each vertex is connected to other vertices). But I still don't know how to formulate a k-plex. How to formulate a maximum size k-plex problem in integer linear programming? Thanks a lot.

Let $x_v$ be a binary variable that takes value $1$ if and only if vertex $v\in V$ is selected. $$ \mbox{Max } n $$ subject to:

1. Define $n$ : $$n=\sum_{u\in V}x_u$$
2. If vertex $v$ is selected, it must have at least $n-k$ neighbours : $$\deg(v)\ge n-k - M(1-x_v)\quad \forall v \in V$$

3. Variables are binary : $$x_v \in \\{0,1\\}$$




$M$ is a large constant, e.g., $M:=|V|$. This way, if $x_v=1$, you have the constraint $\deg(v)\ge n-k$ (i.e., $v$ must have at least $n-k$ neighbours), otherwise the constraint is no longer active.

* * *

EDIT :

If the $n-k$ vertices have to be part of the $k$-plex, then replace the second constraint by $$ \sum_{u\in N_v} x_u\ge n-k - M(1-x_v)\quad \forall v \in V $$ Where $N_v$ denotes the set of vertices adjacent to $v$.