Editing Set cover problem (section)

== Related problems ==
* Hitting set is an equivalent reformulation of Set Cover.
* [[Vertex cover problem|Vertex cover]] is a special case of Hitting Set.
* [[Edge cover problem|Edge cover]] is a special case of Set Cover.
* [[Geometric Set Cover Problem|Geometric set cover]] is a special case of Set Cover when the universe is a set of points in <math>\mathbb{R}^d</math> and the sets are induced by the intersection of the universe and geometric shapes (e.g., disks, rectangles).
* [[Set packing]]
* [[Maximum coverage problem]] is to choose at most k sets to cover as many elements as possible.
* [[Dominating set]] is the problem of selecting a set of vertices (the dominating set) in a graph such that all other vertices are adjacent to at least one vertex in the dominating set. The Dominating set problem was shown to be NP complete through a reduction from Set cover.
* [[Exact cover problem]] is to choose a set cover with no element included in more than one covering set.
* Red-blue set cover.<ref>{{Cite book|last=Information.|first=Sandia National Laboratories. United States. Department of Energy. United States. Department of Energy. Office of Scientific and Technical|url=http://worldcat.org/oclc/68396743|title=On the Red-Blue Set Cover Problem.|date=1999|publisher=United States. Dept. of Energy|oclc=68396743}}</ref>
*[[Set-cover abduction]].
* [[Monotone dualization]] is a computational problem equivalent to either listing all minimal hitting sets or listing all minimal set covers of a given set family.<ref>{{citation
 | last1 = Gainer-Dewar | first1 = Andrew
 | last2 = Vera-Licona | first2 = Paola
 | arxiv = 1601.02939
 | doi = 10.1137/15M1055024
 | issue = 1
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 3590650
 | pages = 63–100
 | title = The minimal hitting set generation problem: algorithms and computation
 | volume = 31
 | year = 2017| s2cid = 9240467
 }}</ref>