-1
  • Given: graph G
  • Input: k
  • Return: "YES" if there exists a set of k nodes, such that no two nodes are connected and no two nodes are connected to the same node. For example if (A,B) and (B,C) then A and C are not allowed in the set of k nodes. How would we prove this problem is NP-complete?

EDIT: I imagine we could use Independent Set/Vertex Cover?

lazycamper
  • 107
  • 1
  • 8
  • Looks like if you complement the graph your are looking for cliques of size k at least... See https://stackoverflow.com/questions/2801138/find-all-complete-sub-graphs-within-a-graph – Jean-Baptiste Yunès May 08 '20 at 14:32

1 Answers1

0

I'm assuming (?) this is a homework problem.

As a hint, start with the dominating set problem.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065