How to formulate a maximum size k-plex problem in integer linear programming?

Question

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 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.4074&rep=rep1&type=pdf

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.

Answer 1

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$.