1
$\begingroup$

We know that the INDEPENDENT-SET problem is NP Complete i.e $\langle G',k'\rangle$ means graph $G'$ has an Independent set of size $k'$. I am preparing for the finals an a sample question is to prove TRIANGLE-FREE-SET to be NP Complete. $$TRIANGLE-FREE-SET:=\{\langle G,k\rangle| \text{$G$ has a subset of vertices of size $k$ whose induced subgraph is triangle free}\}$$

To give a polynomial reduction of IS instance $\langle G',k'\rangle$ to TFS, I thought of adding an extra vertex and connecting this extra vertex to all the original vertex of the IS problem instance and then have $k=k'+1$. However, I am stuck trying to prove that if $\langle G,k\rangle \in TFS$ then $\langle G',k'\rangle \in IS$. Any leads appreciated.

$\endgroup$
3
  • $\begingroup$ Welcome to Computer Science! Let me direct you towards our reference questions which cover, among other things, commonly found reduction techniques. $\endgroup$ – Raphael Dec 14 '17 at 20:03
  • $\begingroup$ I do not see one for reduction from IS, for example. $\endgroup$ – crypto_geek Dec 14 '17 at 20:05
  • 2
    $\begingroup$ The problem with your reduction is that you can "cheat" by not selecting the special vertex. Try having enough special vertices to force at least one to be necessarily chosen. $\endgroup$ – Yuval Filmus Dec 14 '17 at 20:28
1
$\begingroup$

Probably you can get your answer from here: Reducing independent set to triangle-free subgraph

Basically in order to prove that $TFS$ is NP-complete you can just check the first proof in the link's answer. Given a graph $G$ with an independent set $k$, there exists a $G'$ with a $TFS$ of size $|V|+k+1$.

$\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.