Independent Set Problem

computation

Definition

Independent Set Problem

Let $G=(V,E)$ be a graph and $k\in \mathbb{Z}$, whereby $k$ is part of the input (not a constant). The independent set problem is a decision problem asking whether there exists an independent set $S$ such that $|S|\ge k$.

Relation to Vertex Cover

Let $G=(V,E)$ be a graph and $S\subseteq V$ and $C=V-S$. $S$ is an independent set of $G$ if and only if $C$ is a vertex cover of $G$.

Equivalence to Vertex Cover Problem

The independent set problem is equivalent (w.r.t. polynomial time reduction) to the vertex cover problem.

NP-completeness

SAT ${\le }_P$ INDEPENDENT SET

Reduction Idea:

1. Make a clique for each clause (vertices are literals) and set $k$ to be the number of clauses.
   Notice we are now required to choose exactly one literal-vertex in each clique.
2. Next, make each literal-vertex adjacent to each literal-vertex that represented the opposite assignment of the same variable.
   Notice that we are now prevented from choosing incompatible literal-vertices.

Visual Example: Consider the CNF formula $F=(x\vee y)\wedge (\bar{x}\vee y\vee z)\wedge (\bar{y}\vee \bar{z})$.
Here, the number of clauses is $k=3$. We construct a graph where finding an independent set of size $3$ corresponds to satisfying $F$.

Correctness:

• ($\Rightarrow$) Satisfiable $\to$ Independent Set: If $F$ is satisfiable, there is at least one true literal in each clause. By selecting exactly one true literal-vertex from each clause clique, we form a set of size $k=m$. Since we only select true literals, we never select both a variable and its negation, meaning no conflict edges are present. Thus, this forms an independent set of size $k$.
• ($\Leftarrow$) Independent Set $\to$ Satisfiable: If the graph has an independent set of size $k$, it must contain exactly one vertex from each of the $k$ clause cliques (because picking two in the same clique would violate independence). The selected vertices give a consistent truth assignment (because no conflict edges can be selected) that satisfies all $k$ clauses.