3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.