Independent Set Problem

algorithms

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.