Edit the RMarkdown source file for this assignment in RStudio. When you finish, Knit the file to HTML and upload the .html output to Canvas.
Let \(S\) be a set of positive integers, and let \(C\) be a set of subsets of \(S\). A rep set for \(C\) is a subset \(H \subseteq S\) such that \(H\) contains at least one element from each subset in \(C\). For \(S = \{1,2,3,\ldots, 25\}\), find the smallest rep set for the following set of subsets of \(S\). \[\begin{align} C=\{ & \{1,11,14,18,20,23\}, \{5,12,15,18,21,24\}, \{2, 11, 16, 17\}, \\ & \{4, 5, 10,19,24,25\}, \{2,7,17,18,25\}, \{8,11,12,14,16\}, \\ & \{4,6,10,11,22,25\}, \{3,7,12,15,16,19\}, \{1, 6, 9, 12, 14, 19, 21, 24\} \} \end{align}\]
Consider the problem REP-SET: Given a set \(S\) of positive integers, a set \(C\) of subsets of \(S\), find the smallest rep set for \(C\). Prove that REP-SET is NP-hard. (Hint: Read Section 12.14 of [E]: Choosing the Right Problem.) Describe a reduction from an appropriate NP-hard problem, explain why the reduction can be done in polynomial time, and explain why a solver for REP-SET would give you a solver for your chosen problem.