Definition
Maximum Independent Set Optimisation Problem
Instance: A finite simple undirected graph
. Feasible solutions: Independent sets
, meaning for all distinct . Objective: Maximise
:
The goal is a maximum independent set, not merely a maximal one that cannot be extended by another vertex.