Definition: Given a graph G=(V,E) and an integer k, is there a subset of vertices S⊆V such that ∣S∣≥k, and for each edge at most one of its endpoints is in S?