# 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. Dec 14, 2017 at 20:03
• I do not see one for reduction from IS, for example. Dec 14, 2017 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. Dec 14, 2017 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$$.