A k-plex is a graph in which every vertex is adjacent to all but at most k vertices within the graph. Say I have a complete, undirected, weighted graph (a clique and also a k-plex), and I want to remove some edges, in such a way that the sum of the removed edges is maximized and the property of being a k-plex is mantained.
Is there a polynomial time algorithm to solve this?
I know that in general the k-plex editing is NP-hard when we want to edit the graph in such a way that we find many different k-plexes, but in this case I already know the nodes that will be part of the k-plex so maybe this eases this off?
I tried some greedy edge insertion/deletion strategies but ultimately I can always find a case in which they fail. In this example we want a 3-plex starting from a 5 nodes clique (so we can remove max 2 edges per node).
The greedy algorithm prefers removing one expensive edge rather than 2 less expensive edges. We remove 4 edges and then we cannot continue without breaking the splex constraint.
In the optimal solution we remove 5 edges.
