Clique problem

Imagine a group of friends.

In this group, every person knows every other person. In math, we call this a clique.

Finding these groups can be hard. It is like searching for a needle in a haystack. We can use math to find the biggest group.

This helps us in many ways. It can help us find friends in a big crowd. It can even help scientists study tiny parts of life.

Scientists use it to study chemicals. They use it to study how proteins work. Math helps us see how things fit together.

It is a way to find patterns in a big world.

Imagine you are looking at a giant social network.

You want to find a group where every person knows everyone else. 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. This is a group that cannot get any bigger. You might also want to find the maximum clique. This is the largest group possible in the whole graph.

Finding these groups is a very hard task for computers. If a network has many points, a brute-force search takes too much time. A brute-force search means checking every single possible group one by one.

Scientists use these ideas in many real fields. In chemistry, it helps find how molecules fit together. In biology, it helps study how proteins work. It can even help math experts solve puzzles about shapes. Even though it is hard, new ways to find these groups are always being studied.

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.

In the study of graph theory, the clique problem is a fundamental computational challenge. A graph is a mathematical structure made of vertices, which are points, and edges, which are the lines connecting them. A clique is a specific type of subset within a graph known as a complete subgraph. In a clique, every single vertex is connected to every other vertex in that subset by an edge. This means that if you pick any two points in a clique, there is always a direct path between them.

Researchers study several different versions of this problem depending on their goals. One common version is the maximum clique problem, which asks for the largest possible clique in a given graph. The number of vertices in this largest clique is called the clique number. Another version is the maximal clique problem. A maximal clique is a group that cannot be made any larger because no other vertex in the graph is connected to every member of the group. While every maximum clique is maximal, the opposite is not always true.

Other formulations include the weighted maximum clique problem. In this version, each vertex or edge has a specific weight assigned to it. The goal is to find the clique that has the highest total weight rather than just the most vertices. There is also the k-clique problem, where the goal is to find if a clique of a specific size, k, exists. Finally, the clique decision problem asks a simple yes or no question. It tests whether a graph contains a clique larger than a specific number.

Finding these groups is often extremely difficult for computers. The clique decision problem is classified as NP-complete, which is one of Karp's 21 NP-complete problems. This means there is no known way to solve it quickly for all graphs. The maximum clique problem is even more difficult. It is considered fixed-parameter intractable and is hard to approximate. In fact, research from the 1990s showed that, assuming P does not equal NP, it is impossible to even approximate the answer accurately and efficiently.

The history of the term "clique" is rooted in the social sciences rather than pure mathematics. Early mathematical work involved complete subgraphs, such as in the reformulation of Ramsey theory. However, the word "clique" was adopted from sociology to model groups of people who all know one another. Mathematicians Frank Harary and Carl Ross were the first to use this social science terminology in graph theory. They used graphs to represent social networks where vertices were people and edges were mutual acquaintances.

Despite the difficulty, several algorithms exist to help find these structures. A brute-force algorithm can find a k-clique by checking every possible subset of vertices. However, this is too slow for large networks because the time required grows exponentially. For finding maximal cliques, the Bron–Kerbosch algorithm is a well-known method. It can list all maximal cliques in worst-case optimal time. For simpler tasks, a greedy algorithm can find a single maximal clique very quickly by adding vertices one by one.

Clique-finding algorithms have vital applications in many scientific fields. In computational chemistry, they help model molecular docking and chemical reaction binding sites. Scientists create graphs where vertices represent matched pairs of atoms from two different molecules. An edge exists if the matches are compatible, such as having similar distances between atoms. In bioinformatics, these algorithms help predict protein structures and find clusters of interacting proteins. They are also used to infer evolutionary trees.

Mathematics also uses these tools to solve complex theoretical puzzles. For example, the researcher Marijn Heule used a clique-finding algorithm to disprove Keller's conjecture. This conjecture concerned the face-to-face tiling of hypercubes. Heule worked with a massive Keller graph containing 1,048,576 vertices. By finding a clique of size 1,024 within that graph, he provided a counterexample to the conjecture. This demonstrates how even the most abstract mathematical problems can be solved using graph algorithms.