Set cover problem

The set cover problem is a classical question in combinatorics, computer science, operations research, and complexity theory. Given a set of elements {1, 2, …, n} (henceforth referred to as the universe, specifying all possible elements under consideration) and a collection, referred to as S, of a given m subsets whose union equals the universe, the set cover problem is to identify a smallest sub-collection of S whose union equals the universe. For example, consider the universe, U = {1, 2, 3, 4, 5} and the collection of sets S = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }. In this example, m is equal to 4, as there are four subsets that comprise this collection. The union of S is equal to U. However, we can cover all elements with only two sets: { {1, 2, 3}, {4, 5} }‍, but not with only one set. Therefore, the solution to the set cover problem for this U and S has size 2. This example is illustrated in the picture above. More formally, given a universe U {\displaystyle {\mathcal {U}}} and a family S {\displaystyle {\mathcal {S}}} of subsets of U {\displaystyle {\mathcal {U}}} , a set cover is a subfamily C ⊆ S {\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}} of sets whose union is U {\displaystyle {\mathcal {U}}} . In the set cover decision problem, the input is a pair ( U , S ) {\displaystyle ({\mathcal {U}},{\mathcal {S}})} and an integer k {\displaystyle k} ; the question is whether there is a set cover of size k {\displaystyle k} or less. In the set cover optimization problem, the input is a pair ( U , S ) {\displaystyle ({\mathcal {U}},{\mathcal {S}})} , and the task is to find a set cover that uses the fewest sets....