- given a graph and an integer $g$, find $g$ vertices that are independent - independent: no two of them have an edge between them