The weighted s-Plex problem

We consider the Weighted s-Plex Editing Problem (WsPEP), which is a generalization of the s-Plex Editing Problem which in itself is a generalization of the Graph Editing Problem. We are given an undirected graph G=(V,E)G=(VE), a positive integer value ss, and a symmetric weight matrix WW which assigns every (unordered) vertex pair (i,j):i,j∈V,i≠j(ij):ij∈Vi=j a non-negative integer weight wijwij​. An s-Plex of a graph is a subset of vertices S⊆VS⊆V such that each vertex has degree at least ∣S∣−s∣S∣−s and there exist no edges to vertices outside the s-Plex, i.e., i,j∈V,i∈S,j∉S  ⟹  (i,j)∉Eij∈Vi∈Sj∈/S⟹(ij)∈/E. Note that a clique (complete graph on a vertex subset) is a 1-plex. The goal is to edit the edges of the graph by deleting existing edges and/or inserting new edges such that the edited graph consists only of non-overlapping s-Plexes and such that the sum over all weights of the edited edges is minimal. Let a candidate solution be represented by variables xij∈{0,1},i,j∈V,i<jxij​∈{0,1},ij∈Vi<j, where a value 1 indicates that edge (i,j)(ij) is either inserted (if (i,j)∉E(ij)∈/E) or deleted (if (i,j)∈E(ij)∈E) and a value 0 indicates that the edge is not edited. The objective function is then given by min⁡f(x)=∑(i,j)∈Ewijxijminf(x)=∑(ij)∈E​wij​xij​.