Intro

In the set cover problem, there exists a universe set U and a set S of subsets of U. The goal is to pick as few items of S as possible such that their union is equal to the set U.

This version of the problem, where we are trying to find the minimum number of elements of S such that their union is equal to S, is NP-hard. In practice, this means that this problem cannot be solved exactly nor verified efficiently. Thus, aside from approximations, the best we can do for this problem is write efficient solvers which prune off as many unnecessary calculations as possible.

I wrote a solver which I will soon make public. (Waiting on permission from a professor)

Naive Idea

The most naive idea is to write a solver where you try every possible subset of S and find the smallest S whose union is U, but this will run with a worst case time complexity of roughly \(O(|U|\cdot 2^{|S|})\) depending on implementation. If |S| is large, meaning even just 40 or larger, this will take hours, days, or possibly even years to run.

Optimizations

There are several interesting concepts to explore within this project.

  • Constant time optimization
    • This is very much affected by choice of data structures and algorithms. To drop my overhead as much as possible, I represent sets of elements using bitsets since I can always compress them into a small range. This also allows me to do set operations efficiently using bitwise operations
  • We can reconsider this problem as search on an implicit tree where successfully reaching a leaf of the tree implies that we have found a solution. Then, the problem becomes about reducing the size of the tree as much as possible, and searching the rest that we could not reduce as fast as possible. The solution to the problem becomes the minimum value we find across all of the leaves of the tree.