I have a variation of the NP-hard minimum clique cover problem. My problem reduces to that problem, so is also NP-hard.
We have n sets of vertices. Each set has between 1 and k vertices. Let's assume that n is at most 210 and k is at most 10.
There are edges between some but not all pairs of vertices that belong to different sets, and no edges between vertices in the same set. I don't yet know how likely any given pair of vertices in different sets is to have an edge between them, but we can assume many but not all of these potential edges exist.
We need to find the minimum collection of cliques such that each of our n sets of vertices has a vertex in at least one clique. Assuming this is effectively impossible given the NP-hard nature of the problem and the size of n and k, can we find a reasonable approximation?
For clarity, I expect that exactly one vertex from each set will be in the solution, and that we'll have either the minimum number of cliques that covers that set, or some approximation of it.
My best idea so far is to pick n vertices that form a relatively dense graph, and then apply existing techniques for minimum clique covers/approximations to that. I could pick the vertices by greedily choosing the highest degree in succession, where for latter picks I exclude edges to vertices that have been eliminated because some other vertex in the same set has been chosen.