2
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ Much clearer, I'll delete my comment (but re-mention that $|N|=1$ also works ;) ) $\endgroup$
    – j_random_hacker
    May 19, 2020 at 22:21
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Steven
    May 19, 2020 at 22:28
  • $\begingroup$ Ah, you're right -- we could not guarantee that $S' \cap N \ne \emptyset$ if $|N|=1$. $\endgroup$
    – j_random_hacker
    May 19, 2020 at 22:37
  • $\begingroup$ Exactly :) $\phantom{}$ $\endgroup$
    – Steven
    May 19, 2020 at 22:37

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.