Reducing 3SAT to Triangle Cover Graph

Question

The Triangle Cover Graph problem is this:

Given a graph $G = (V,E)$ and an integer $k$, does there exist a set of at most $k$ vertices of $G$ such that every triangle contained in $G$ also contains a vertex of the set?

This problem is obviously in $NP$ as its verifier is just the set which you can easily check. However, what's the reduction to be able to show that this is NP Complete?

I recognize the fact that a good reduction for this problem would be for 3-SAT as you could easily take a 3-sat instance and make a 3-vertex triangle in the graph corresponding to the variables which are in each clause. However, I wasn't able to come up with a way to connect the different triangles together to ensure that the assignment of vertices would be a satisfiable truth assignment.

Answer 1

Hint: The obvious thing to do would be to have two vertices $v^+,v_-$ per variable and one triangle per constraint. You might have to tweak this construction a little to avoid the possibility that both truth values are selected for some variable. You can do this using a "gadget", one per variable, that forces the selection of at least one truth value per variable.