Exact cover problem but with constraint on exact number of subsets in the solution

Question

I'm relatively new to exact-cover and similar problems, so please bear with me. Suppose I have a typical exact-cover problem, ie. given a set X and a collection of X's subsets S, I want to find S* (a subset of S) that exact-covers X. However, I want the solution S* to contain exactly k elements. Moreover, one solution is enough.

I know that Knuth's Algorithm X is designed to return all possible solutions. Should I just run Knuth's Algorithm and iterate through the solutions until I find one with k elements, or is there (as I suspect) a much better way? I'm using Python btw.

For context, X's size is <100 but S's size can be 10^6. k is relatively small at <10.

Answer 1

If k is small, you might simply try adding k extra elements, and duplicate each subset k times with each duplicate including exactly one of the k extra elements.

Another approach would be to solve the exact cover problem as an integer linear program, and solve it with an ILP solver. Then you'll have 0-1 variables x_i that say whether the ith subset is included in a solution, with constraints that prevent overlapping sets being included in the solution. In this formulation, to provide a cover with exactly k subsets, you'll simply have the additional constraint that sum(x_i) = k.

It's also possible to modify algorithm X to deal directly with the constraint. Just count how many rows you've chosen so far, and if you've already chosen k, just fail without searching further. Similarly, ignore solutions that have fewer than k rows.