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

$\endgroup$
2
$\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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Much clearer, I'll delete my comment (but re-mention that $|N|=1$ also works ;) ) $\endgroup$ – j_random_hacker May 19 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 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 at 22:37
  • $\begingroup$ Exactly :) $\phantom{}$ $\endgroup$ – Steven May 19 at 22:37

Your Answer

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

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