# NP Complete Proof - Polynomial Reduction

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.

• Welcome to Computer Science! Let me direct you towards our reference questions which cover, among other things, commonly found reduction techniques. – Raphael Dec 14 '17 at 20:03
• I do not see one for reduction from IS, for example. – crypto_geek Dec 14 '17 at 20:05
• 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. – Yuval Filmus Dec 14 '17 at 20:28

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