Clique problem

Imagine you are looking at a map of a huge social network.

Each dot on the map is a person. The lines between the dots show who knows each other. You might want to find a special group where every single person knows every other person in that group. In math, we call this group a clique. A clique is a part of a graph where every point is connected to every other point by a line. There are different ways to look for these groups. You might want to find a maximal clique, which is a group that cannot get any larger. You might also want to find the maximum clique, which is the biggest group possible in the whole graph.

Finding these groups can be a very hard job for computers. One way to find them is a brute-force search. This means checking every possible group one by one to see if it works. This takes a very long time if the network is large. For a network with many points, this method is not practical. Scientists have found that finding the largest clique is a hard problem to solve or even to guess. Some versions of the problem are known as NP-complete. This means they belong to a group of very difficult math problems. Even finding a list of all maximal cliques can take an enormous amount of time.

People have studied these groups for a long time. The idea of complete subgraphs appeared in math before we used the word "clique." The term "clique" actually comes from the social sciences. Researchers used it to describe groups of people who all know each other. Mathematicians like Frank Harary and Carl Ross helped bring this idea into graph theory. They used graphs to model social networks. They were the first to call these complete subgraphs "cliques." Since then, many other people have created new ways to find them.

Different researchers have found different ways to solve these puzzles. In the 1970s, experts began studying how hard these tasks really are. They used something called worst-case analysis to measure the difficulty. In the 1990s, new papers showed that it is hard to even get close to the right answer quickly. One helpful tool is the Bron–Kerbosch algorithm. This can be used to list all maximal cliques in a very efficient way. Some problems can be solved faster if the graph has a special shape. For example, finding cliques in planar graphs is much easier for a computer.

These math ideas are useful in many real-world jobs. In chemistry, clique-finding helps scientists see how molecules fit together. They can find chemicals that match a specific target structure. In biology, these algorithms help scientists study proteins. They can use them to predict protein structures or find clusters of proteins that work together. Even in pure math, these tools help solve big puzzles. For example, a researcher named Marijn Heule used a clique-finding algorithm to disprove Keller's conjecture. He used a massive graph with 1,048,576 vertices to find his answer.