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.

Improve this question
$\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, 2017 at 20:03
  • $\begingroup$ I do not see one for reduction from IS, for example. $\endgroup$
    – crypto_geek
    Dec 14, 2017 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, 2017 at 20:28

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.