Maximum Independent Set Optimisation Problem

Definition

Maximum Independent Set Optimisation Problem

Instance: A finite simple undirected graph $G=(V,E)$.

Feasible solutions: Independent sets $I\subseteq V$, meaning $\{u,v\}\notin E$ for all distinct $u,v\in I$.

Objective: Maximise $|I|$:
$\alpha (G)=\max \{|I|:I\subseteq V,\forall e\in E:|e\cap I|\le 1\}.$
The goal is a maximum independent set, not merely a maximal one that cannot be extended by another vertex.