Given a set of elements called the universe an a collection of subsets whose union equals to the universe, the set cover problem is to identify the smallest subset collection of whose union equals to the universe.
Let’s say the universe is and , then the minimal subset that covers the whole universe is .
The set cover problem can also be divided into a decision problem and an optimization problem:
- Decision problem: given and an integer , output if there is a set cover of size or less.
- Optimization problem: given and , find a set cover that uses the fewest sets.
The decision problem is -complete, while the optimization version of the problem is -hard.
Equivalence with the Hitting Set Problem
The set cover problem it’s equivalent to the Hitting Set Problem.
That is seen by observing that an instance of set covering can be viewed as an arbitrary bipartite graph, with the universe represented by vertices on the left, the sets represented by vertices on the right, and edges representing the membership of elements to sets. The task is then to find a minimum cardinality subset of left-vertices that has a non-trivial intersection with each of the right-vertices, which is precisely the hitting set problem.
tags: computation-theory resources: Set cover problem - Wikipedia