Problem Definition Given a graph G=(V,E) and an integer k, is there a subset of k vertices such that no two are adjacent?