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.

  • $\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
  • 1
    $\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

Your Answer

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

Browse other questions tagged or ask your own question.