Given the fixed $k$, you could look at all $\binom{n}{k}$ subsets of vertices to see if they form a clique of size $k$ (or do whatever you like to enumerate all cliques of size $k$ -- there might be a variation of Bron-Kerbosch for that). List all your sets of $k$ vertices which violate the structure you seek.

To maximize your selected vertices in your question, you are looking to remove the minimum number of vertices which will 'hit' all your constructed $k$-sets. This is the HITTING-SET problem. Beware that your $k$ value will be the $d$ in the $d$-HITTING-SET problem in most references, while "$k$" will normally be reserved for the number of vertices that will be removed.

The bad news is that HITTING-SET is NP-Complete but the good news:

- it is Fixed-parameter tractable and there are good exact algorithms for it
- is
**very** well-studied
- there are fast approximation algorithms / heuristics with provable bounds
- most solutions generalize to hitting sets where the input sets are not all of equal size, and vertex-weighted variants
- hitting set solves a lot of other problems where you are trying to find the max number of vertices with an avoidance property (through the means of removing the fewest number of vertices from subsets that have that property)
- there are implementations of the problem of finding the hitting set: https://github.com/VeraLiconaResearchGroup/Minimal-Hitting-Set-Algorithms

(This implementation finds all minimal hitting sets, from which you can pick your favorite smallest one, or you can apply a parameter to only generate hitting sets up to a certain size)