# Reducing independent set to triangle-free subgraph

The INDEPENDENT-SET problem is a well-known NP complete problem that takes in a graph $$G$$ and an integer $$k$$. It returns true if $$G$$ has an independent set of size $$k$$.

An instance of the TFS (triangle-free-set) problem takes in a graph $$G$$ and an integer $$k$$ and it returns true iff $$G$$ has a subset of size $$k$$ whose induced subgraph is triangle free.

I want to perform a polynomial-time reduction of IS to an instance of triangle-free-set. So I start off with an instance of INDEPENDENT-SET, and I want to reduce it to an instance of TFS. But I'm not quite sure how to do this. I tried many things, like adding additional vertices for each pair of vertices, but I don't think this is right. I also saw a similar question here: NP Complete Proof - Polynomial Reduction, but I cannot quite figure out the approach from just that one person's question.

I would greatly appreciate any help.

Let $$\langle G=(V, E), k \rangle$$ be an instance of Independent Set, and call $$n=|V|$$. Let $$N$$ be a set of $$n+1$$ new vertices (not in $$V$$), and construct a new graph $$G' = (V', E')$$ where $$V' = V \cup N$$ and $$E' = E \cup (N \times V)$$.

If $$G$$ has an Independent Set $$S$$ of size at least at least $$k$$ then $$G'$$ has a Triangle-Free set $$S'$$ of size at least $$n+k+1$$.

Select $$S' = S \cup N$$. To see that the subgraph of $$G'$$ induced by $$S'$$ is triangle free consider any triple $$(a,b,c)$$ of distinct vertices in $$S'$$. Clearly, if more than one of $$a$$, $$b$$, and $$c$$ is in $$N$$, the triple cannot induce a triangle since $$G'$$ has no edges between vertices in $$N$$. On the other hand, if at least two distinct vertices $$u,v \in \{a, b, c\}$$ are in $$S$$, then $$(u,v) \not \in E$$ and hence $$(u,v) \not\in E'$$.

If $$G$$ has a Triangle-Free set $$S'$$ of size at least $$n+k+1$$ then $$G'$$ has an Independent Set $$S$$ of size at least at least $$k$$.

Let $$S=S' \setminus N$$. Since $$|S| \ge n+k+1$$ and $$|N|=n+1$$, the cardinality of $$S$$ is at least $$k$$. To see that $$S$$ is an Independent Set of $$G$$ notice that $$S' \cap N \neq \emptyset$$ and let $$v \in S' \cap N$$. Let $$a$$ and $$b$$ be any two distinct vertices in $$S$$. Since the subgraph of $$G'$$ induced by $$S'$$ is triangle free and $$\{(v,a), (v,b) \} \subseteq E'$$, we must have $$(a,b) \not\in E' \supseteq E$$.

• Much clearer, I'll delete my comment (but re-mention that $|N|=1$ also works ;) ) – j_random_hacker May 19 at 22:21
• I picked $|N|=n+1$ to ensure that at least one vertex $v$ from $N$ must always be included in any triangle-free set $S'$ of size $n+k+1$, which ensures that $S\setminus N$ is an independent set. If $N$ only contained a single vertex then, it could be possible to select, for example, a triangle-free set $S'$ that consists of 1) an independent set of size $k-1$ in $G$ plus 2) two additional non-adjacent vertices, each of which is a neighbor of exactly one of the vertices of the independent set (so it doesn't close any triangle). Now the largest subset of $S'$ that is independent has size $k-1$. – Steven May 19 at 22:28
• Ah, you're right -- we could not guarantee that $S' \cap N \ne \emptyset$ if $|N|=1$. – j_random_hacker May 19 at 22:37
• Exactly :) $\phantom{}$ – Steven May 19 at 22:37