Why finding the perfect social circle is a notoriously hard computational problem

Why finding the perfect social circle is a notoriously hard computational problem
Image: Intellect (generated)

In short: In computer science, a clique is a group where everyone is connected to everyone else. While this sounds simple, identifying the largest such group in a network is an NP-complete problem. It is so computationally demanding that even for modest networks, brute-force searches quickly become impossible to complete.

The clique problem originated in the social sciences, where researchers like Luce and Perry in 1949 used graph theory to model mutual acquaintances. In this framework, vertices represent individuals, and edges represent friendships. A clique is a subset of people who all know one another. While the concept is intuitive, the computational challenge of finding the largest clique—the maximum clique—is immense. Most versions of this problem are NP-complete, meaning they are among the hardest problems to solve efficiently.

For small networks, one might try a brute-force approach by inspecting every possible subset of vertices. However, this method is impractical for networks with more than a few dozen vertices. Because no polynomial-time algorithm is known for the general maximum clique problem, researchers focus on identifying special graph types where efficient solutions exist. For instance, in perfect graphs, the maximum clique can be found in polynomial time using semidefinite programming, while planar graphs allow for linear-time listing of cliques due to their sparse structure.

Beyond social networks, clique-finding is vital in bioinformatics for protein structure prediction and in chemistry for molecular docking. In these applications, graphs are constructed where vertices represent matched pairs of atoms, and edges signify compatibility. Finding a maximum clique in such a graph reveals the largest set of mutually compatible matches. Despite the difficulty, algorithms like Bron–Kerbosch provide optimal ways to list maximal cliques, and researchers continue to refine heuristic methods and specialized algorithms to tackle the problem's inherent complexity.

Opens the Intellect+ feed with this card first. Swipe up for the next one.

Sources

To cite this card, link to https://intellectplus.co.uk/app/science-clique-problem.

How we source, check and correct cards: Editorial standards.

General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.

Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?

Related

Finding something worth knowing…