# Find largest subset of vertices in graph so that every pair of vertices have an edge between them

Let's say you have a graph like this:

The largest subset of nodes so that every pair of vertices have an edge between them is $\{3, 5, 7, 12\}$. The second largest subsets are

• $\{4, 7, 21\}$,
• $\{3, 5, 7\}$,
• $\{3, 5, 12\}$,

etc.

Is there an algorithm to find the largest subset efficiently?

Also, keep in mind that I know virtually nothing about graphs (haven't learned at school, haven't taught myself). The data was originally given as a set of pairs of numbers.

• This problem is called Maximum Clique, and unfortunately it's NP-hard, meaning it's very unlikely that any algorithm exists that can solve every instance quickly. Jun 2, 2018 at 14:49
• If you want to find a maximum clique (or even enumerate all of them), there are good solvers for that available.
– Juho
Jun 3, 2018 at 9:55

This is called the Maximum Clique Problem, and it's NP-hard. The decision problem version, "is there a clique with size $k$?", is in fact NP-complete. So an efficient solution to the Maximum Clique Problem would prove that P=NP and earn you the \$1,000,000 prize and eternal fame.