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.
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 i
th 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.