0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$).
$\endgroup$
  • $\begingroup$ But the question was to find such a set in G not G' $\endgroup$ – darkodarko Nov 16 '17 at 17:09
  • $\begingroup$ For an NP-completeness reduction, we want to turn an arbitrary instance of the VERTEX COVER decision problem into an equivalent instance of PROBLEM. If there were an efficient way to solve PROBLEM, it would therefore give us an efficient way to solve VERTEX COVER. $\endgroup$ – Misha Lavrov Nov 16 '17 at 17:33
  • $\begingroup$ I understand that but it's still hard zo imagine the equivallence, I even drew a simple graph but still don't see what you meant $\endgroup$ – darkodarko Nov 16 '17 at 17:43
  • $\begingroup$ 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. $\endgroup$ – Misha Lavrov Nov 16 '17 at 18:00
  • $\begingroup$ 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$. $\endgroup$ – Fabio Somenzi Nov 16 '17 at 21:39

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.