hitting_set (826B)
1 # Hitting set 2 3 Given a family of sets on a universe, find a smallest subset of elements that 4 intersects every set in the family 5 6 The [dual] is the [set_cover] problem: find the smallest subset of sets whose 7 union is equal to the universe. This duality is explained here 8 <https://en.wikipedia.org/wiki/Set_cover_problem#Hitting_set_formulation>. 9 Indeed, when considering the set of occurrences of every element for the set cover problem (the new sets), we want to find a subset of elements (the original sets) that intersects every new set (= the original elements), i.e., a subset of the original sets such that every original element is contained in a set of the subset. 10 11 In [computational_geometry]: "stabbing" or "piercing" cf [nielsen2000fast] 12 13 Up: [computational_problem] on [set] 14 15 See also: [small_universe_hitting_set]