Independent set of a given size

Statement

Independent set of a given size

Given a undirected graph and positive integer . Does have an independent set of size ?

Solutions

• First solution
  • run time

Theory

• Independent set of a given size is in NP
• Independent set of a given size is NP-complete

Related problems

• Max independent set problem (graph)