# Prove NP completness using reduction to Vertex Cover

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?

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$).
• Essentially, to cover all the triangles of the form $(w_i, v_j, v_k)$ we either need to include $w_i$ in the cover or to cover all edges $(v_j, v_k)$. We can't include all the $w_i$ in the cover. – Misha Lavrov Nov 16 '17 at 18:00
• Perhaps it's worth adding that from every triangle cover of size $k'$ that includes vertices from $\{w_1,\ldots,w_{k+1}\}$ one can easily derive another cover of size at most $k'$ that only includes vertices from $V$. It is this derived triangle cover that, when $k' \leq k$, witnesses the existence of a vertex cover for $G$. – Fabio Somenzi Nov 16 '17 at 21:39