If NP-complete, prove another is also NP-complete

Question

I've been trying to work on this problem but I don't really know where to start and can't find any resources online. Would it be possible for someone to guide me through step by step.

Answer 1

The vertices in VC "cover" every $edge$ (u, v) in G
This just means that every $edge$ (u, v) has at least one of its $vertices$ (u or v) in VC

The elements in HS "cover" every $subset$ $S_i$ in U
This just means that every $subset$ $S_i$ has at least one of its $elements$ in HS

Notice how the problems are "similar"
The $edges$ in the VC problem correspond to $subsets$ in the HC problem
The $vertices$ in the VC problem correspond to the $elements$ in the HS problem

This gives an idea for how to reduce VC to HS.
For every edge (u, v) in G, add the subset {u, v} to U.

To prove that our reduction works, we have to prove:
$\quad$G has a VC of size $\le k \iff$ U has a HS of size $\le k$

G has a VC of size $\le k$
$\quad \Rightarrow$ every $edge$ (u, v) in G has at least one of its $vertices$ (u or v) in VC
$\quad \Rightarrow$ every $subset$ {u, v} in U has at least one of its $elements$ (u or v) in HS (by setting HS = VC) $\quad\Rightarrow$ U has a HS of size $\le k$

U has a HS of size $\le k$
$\quad \Rightarrow$ every $subset$ {u, v} in U has at least one of its $elements$ (u or v) in HS
$\quad \Rightarrow$ every $edge$ (u, v) in G has at least one of its $vertices$ (u or v) in VC (by setting VC = HS)
$\quad\Rightarrow$ G has a VC of size $\le k$