Prove NP completness using reduction to Vertex Cover

Question

Let the input be a graph $G=(V,E)$ and $k\in \mathbb{N}$. Does there exist a set $S\subset V$ such that $S$ contenis at least one node from each triangle in $G$ (clique of size 3) such that $|S|\leq k$.

I have to prove that this is $NP$ complete. It's obvious that PROBLEM $\in NP$. I want to show, or rather I am trying to, that $VERTEX\ COVER \propto \ PROBLEM$. Any ideas?

Answer 1

Take a graph $G = (V,E)$ for which you want to solve the vertex cover problem, together with the input $k$, and let $G'$ be the graph whose vertex set is $V \cup \{w_1, w_2, \dots, w_{k+1})$ and whose edge set is $E \cup \{vw_i : v \in V, 1 \le i \le k+1\}$.

Then a "vertex triangle cover" of $G'$ with size $\le k$ exists if and only if a vertex cover of $G$ with size $\le k$ exists, and we can go from one to the other as follows:

• Given a vertex cover of $G$, the same set of vertices is also a vertex triangle cover of $G'$. All triangles contained in $G$ are covered because each of their edges is covered; all triangles $\{w_i, v, v'\}$ are covered because the edge $vv'$ is covered.
• Given a vertex triangle cover of $G'$ of size at most $k$, its intersection with $V$ is a vertex cover of $G$. There must be some $w_i$ that is not in the vertex triangle cover; then each edge $vv'$ of $G$ must be covered because the triangle $\{w_i, v, v'\}$ is covered (and not by $w_i$).