1
$\begingroup$

Let's say you have a graph like this:

example

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – j_random_hacker
    Jun 2, 2018 at 14:49
  • 1
    $\begingroup$ If you want to find a maximum clique (or even enumerate all of them), there are good solvers for that available. $\endgroup$
    – Juho
    Jun 3, 2018 at 9:55

1 Answer 1

Reset to default
2
$\begingroup$

Unfortunately, the answer is no.

In graph theory, such a subset is called a clique. (Essentially, a graph is a set of nodes and a set of edges between those nodes, and a clique is a set of nodes in a graph such that every node in the set has an edge to every other node in the set.) What you want is to find the largest clique in a given graph.

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.