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\le210$ and $k\le10$.
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 exactly one vertex in at least one clique. Assuming that finding the minimum 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, exactly one vertex from each set will be in the solution, and we'll have either the minimum number of cliques that covers the vertices in the solution, or some approximation of it.
I would appreciate any help finding a solution or approximation, or links to any research others have done on this or related problems.