Clique of a given size problem

Statement

Clique of a given size problem

Given an undirected graph and a positive integer . Does there exist a clique of size at least if so what is it?

Solutions

Theory

• Clique of a given size problem is in NP
• Clique of a given size problem is NP-complete

Related problems

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