Editing Set cover problem (section)

{{Short description|Classical problem in combinatorics}}

[[File:SetCover.svg|thumb|Example of an instance of set cover problem.]]
The '''set cover problem''' is a classical question in [[combinatorics]], [[computer science]], [[operations research]], and [[Computational complexity theory|complexity theory]].  

Given a [[Set (mathematics)|set]] of elements {{math|{1, 2, …, ''n''} }}(henceforth referred to as the [[Universe (mathematics)|universe]], specifying all possible elements under consideration) and a collection, referred to as {{mvar|S}}, of a given {{mvar|m}} subsets whose [[union (set theory)|union]] equals the universe, the set cover problem is to identify a smallest sub-collection of {{mvar|S}} whose union equals the universe. 

For example, consider the universe, {{math|1=''U'' = {1, 2, 3, 4, 5<nowiki>}</nowiki> }} and the collection of sets {{math|1=''S'' = { {1, 2, 3}, {2, 4}, {3, 4}, {4, 5} }.}} In this example, {{mvar|m}} is equal to 4, as there are four subsets that comprise this collection. The union of {{mvar|S}} is equal to {{mvar|U}}. However, we can cover all elements with only two sets: {{math|{ {1, 2, 3}, {4, 5} }‍}}, see picture, but not with only one set. Therefore, the solution to the set cover problem for this {{mvar|U}} and {{mvar|S}} has size 2.

More formally, given a universe <math>\mathcal{U}</math> and a family <math>\mathcal{S}</math> of subsets of <math>\mathcal{U}</math>, a '''set cover''' is a subfamily <math>\mathcal{C}\subseteq\mathcal{S}</math> of sets whose union is <math>\mathcal{U}</math>. 

* In the set cover [[decision problem]], the input is a pair <math>(\mathcal{U},\mathcal{S})</math> and an integer <math>k</math>; the question is whether there is a set cover of size <math>k</math> or less.
* In the set cover [[optimization problem]], the input is a pair <math>(\mathcal{U},\mathcal{S})</math>, and the task is to find a set cover that uses the fewest sets.

The decision version of set covering is [[NP-complete]]. It is one of [[Karp's 21 NP-complete problems]] shown to be [[NP-complete]] in 1972. The optimization/search version of set cover is [[NP-hard]].{{sfn |Korte|Vygen|2012|p=414}} It is a problem "whose study has led to the development of fundamental techniques for the entire field" of [[approximation algorithms]].<ref>{{harvtxt|Vazirani|2001|p=15}}</ref>