Max independent set problem (graph)

Statement

Max independent set problem

Given a undirected graph what is the size of the largest independent set in ?

Solutions

• First solution
  • run time

Theory

• Max independent set problem is NP-hard

Related problems

• Independent set of a given size
• Max clique problem (graph)