# Set Cover

 Input Output

Input Description: A set of subsets $$S_1, ..., S_m$$ of the universal set $$U = \{1,...,n\}$$.
Problem: What is the smallest subset of subsets $$T \subset S$$ such that $$\cup_{t_i \in T} t_i = U$$?

Excerpt from The Algorithm Design Manual: Set cover arises when you try to efficiently acquire or represent items that have been packaged in a fixed set of lots. You want to obtain all the items, while buying as few lots as possible. Finding a cover is easy, because you can always buy one of each lot. However, by finding a small set cover you can do the same job for less money.

An interesting application of set cover is Boolean logic minimization. We are given a particular Boolean function of $$k$$ variables, which for each of the $$2k$$ possible input vectors describes whether the desired output is $$0$$ or $$1$$. We seek the simplest circuit that exactly implements this function. One approach is to find a disjunctive normal form (DNF) formula on the variables and their complements, such as $$x1 \bar x2 + \bar{x}1 \bar{x}2$$. We could build one and'' term for each input vector and then or'' them all together, but we might save considerably by factoring out common subsets of variables. Given a set of feasible and'' terms, each of which covers a subset of the vectors we need, we seek to or'' together the smallest number of terms that realize the function. This is exactly the set cover problem.

### Related Problems

 Matching Polygon Partitioning Set Data Structures Set Packing Vertex Cover

Go To Main Page