In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique (a clique with the largest possible number of vertices), finding a maximum weight clique in a weighted graph, listing all maximal cliques (cliques that cannot be enlarged), and solving the decision problem of testing whether a graph contains a clique larger than a given size.
The clique problem arises in the following real-world setting. Consider a social network, where the graph's vertices represent people, and the graph's edges represent mutual acquaintance. Then a clique represents a subset of people who all know each other, and algorithms for finding cliques can be used to discover these groups of mutual friends. Along with its applications in social networks, the clique problem also has many applications in bioinformatics, and computational chemistry.
Most versions of the clique problem are hard. The clique decision problem is NP-complete (one of Karp's 21 NP-complete problems). The problem of finding the maximum clique is both fixed-parameter intractable and hard to approximate. And, listing all maximal cliques may require exponential time as there exist graphs with exponentially many maximal cliques. Therefore, much of the theory about the clique problem is devoted to identifying special types of graphs that admit more efficient algorithms, or to establishing the computational difficulty of the general problem in various models of computation.
To find a maximum clique, one can systematically inspect all subsets, but this sort of brute-force search is too time-consuming to be practical for networks comprising more than a few dozen vertices. Although no polynomial time algorithm is known for this problem, more efficient algorithms than the brute-force search are known. For instance, the Bron–Kerbosch algorithm can be used to list all maximal cliques in worst-case optimal time, and it is also possible to list them in polynomial time per clique.
History and applications The study of complete subgraphs in mathematics predates the "clique" terminology. For instance, complete subgraphs make an early appearance in the mathematical literature in the graph-theoretic reformulation of Ramsey theory by . But the term "clique" and the problem of algorithmically listing cliques both come from the social sciences, where complete subgraphs are used to model social cliques, groups of people who all know each other. used graphs to model social networks, and adapted the social science terminology to graph theory. They were the first to call complete subgraphs "cliques". The first algorithm for solving the clique problem is that of ,; . who were motivated by the sociological application. Social science researchers have also defined various other types of cliques and maximal cliques in social network, "cohesive subgroups" of people or actors in the network all of whom share one of several different kinds of connectivity relation. Many of these generalized notions of cliques can also be found by constructing an undirected graph whose edges represent related pairs of actors from the social network, and then applying an algorithm for the clique problem to this graph.
Since the work of Harary and Ross, many others have devised algorithms for various versions of the clique problem. In the 1970s, researchers began studying these algorithms from the point of view of worst-case analysis. See, for instance, , an early work on the worst-case complexity of the maximum clique problem. Also in the 1970s, beginning with the work of and , researchers began using the theory of NP-completeness and related intractability results to provide a mathematical explanation for the perceived difficulty of the clique problem. In the 1990s, a breakthrough series of papers beginning with showed that (assuming P ≠ NP) it is not even possible to approximate the problem accurately and efficiently.
Clique-finding algorithms have been used in chemistry, to find chemicals that match a target structure and to model molecular docking and the binding sites of chemical reactions. They can also be used to find similar structures within different molecules.. See in particular pp. 35–36. In these applications, one forms a graph in which each vertex represents a matched pair of atoms, one from each of two molecules. Two vertices are connected by an edge if the matches that they represent are compatible with each other. Being compatible may mean, for instance, that the distances between the atoms within the two molecules are approximately equal, to within some given tolerance. A clique in this graph represents a set of matched pairs of atoms in which all the matches are compatible with each other.. See in particular pp. 6–7. A special case of this method is the use of the modular product of graphs to reduce the problem of finding the maximum common induced subgraph of two graphs to the problem of finding a maximum clique in their product.
In automatic test pattern generation, finding cliques can help to bound the size of a test set. In bioinformatics, clique-finding algorithms have been used to infer evolutionary trees, predict protein structures, and find closely interacting clusters of proteins. Listing the cliques in a dependency graph is an important step in the analysis of certain random processes. In mathematics, Keller's conjecture on face-to-face tiling of hypercubes was disproved by , who used a clique-finding algorithm on an associated graph to find a counterexample.The Keller graph used by has 1048576 vertices and clique size 1024. They described a synthetic construction for the clique, but also used clique-finding algorithms on smaller graphs to help guide their search. simplified the proof by finding a clique of size 256 in a 65536-vertex Keller graph.
Definitions
An undirected graph is formed by a finite set of vertices and a set of unordered pairs of vertices, which are called edges. By convention, in algorithm analysis, the number of vertices in the graph is denoted by and the number of edges is denoted by . A clique in a graph is a complete subgraph of . That is, it is a subset of the vertices such that every two vertices in are the two endpoints of an edge in . A maximal clique is a clique to which no more vertices can be added. For each vertex that is not part of a maximal clique, there must be another vertex that is in the clique and non-adjacent to , preventing from being added to the clique. A maximum clique is a clique that includes the largest possible number of vertices. The clique number is the number of vertices in a maximum clique of .
Several closely related clique-finding problems have been studied.; . In the maximum clique problem, the input is an undirected graph, and the output is a maximum clique in the graph. If there are multiple maximum cliques, one of them may be chosen arbitrarily. In the weighted maximum clique problem, the input is an undirected graph with weights on its vertices (or, less frequently, edges) and the output is a clique with maximum total weight. The maximum clique problem is the special case in which all weights are equal. As well as the problem of optimizing the sum of weights, other more complicated bicriterion optimization problems have also been studied. In the maximal clique listing problem, the input is an undirected graph, and the output is a list of all its maximal cliques. The maximum clique problem may be solved using as a subroutine an algorithm for the maximal clique listing problem, because the maximum clique must be included among all the maximal cliques. In the -clique problem, the input is an undirected graph and a number . The output is a clique with vertices, if one exists, or a special value indicating that there is no -clique otherwise. In some variations of this problem, the output should list all cliques of size . In the clique decision problem, the input is an undirected graph and a number , and the output is a Boolean value: true if the graph contains a -clique, and false otherwise. The first four of these problems are all important in practical applications. The clique decision problem is not of practical importance; it is formulated in this way in order to apply the theory of NP-completeness to clique-finding problems.
The clique problem and the independent set problem are complementary: a clique in is an independent set in the complement graph of and vice versa., Exercise 34-1, p. 1018. Therefore, many computational results may be applied equally well to either problem, and some research papers do not clearly distinguish between the two problems. However, the two problems have different properties when applied to restricted families of graphs. For instance, the clique problem may be solved in polynomial time for planar graphs; . while the independent set problem remains NP-hard on planar graphs.
Algorithms
Finding a single maximal clique A maximal clique, sometimes called inclusion-maximal, is a clique that is not included in a larger clique. Therefore, every clique is contained in a maximal clique.See, e.g., . Maximal cliques can be very small. A graph may contain a non-maximal clique with many vertices and a separate clique of size 2 which is maximal. While a maximum (i.e., largest) clique is necessarily maximal, the converse does not hold. There are some types of graphs in which every maximal clique is maximum; these are the complements of the well-covered graphs, in which every maximal independent set is maximum. However, other graphs have maximal cliques that are not maximum.
A single maximal clique can be found by a straightforward greedy algorithm. Starting with an arbitrary clique (for instance, any single vertex or even the empty set), grow the current clique one vertex at a time by looping through the graph's remaining vertices. For each vertex that this loop examines, add to the clique if it is adjacent to every vertex that is already in the clique, and discard otherwise. This algorithm runs in linear time., p. 526. Because of the ease of finding maximal cliques, and their potential small size, more attention has been given to the much harder algorithmic problem of finding a maximum or otherwise large clique. However, some research in parallel algorithms has studied the problem of finding a maximal clique. In particular, the problem of finding the lexicographically first maximal clique (the one found by the algorithm above) has been shown to be complete for the class of polynomial-time functions. This result implies that the problem is unlikely to be solvable within the parallel complexity class NC.
Cliques of fixed size One can test whether a graph contains a -vertex clique, and find any such clique that it contains, using a brute force algorithm. This algorithm examines each subgraph with vertices and checks to see whether it forms a clique. It takes time , as expressed using big O notation. This is because there are subgraphs to check, each of which has edges whose presence in needs to be checked. Thus, the problem may be solved in polynomial time whenever is a fixed constant. However, when does not have a fixed value, but instead may vary as part of the input to the problem, the time is exponential.E.g., see .
The simplest nontrivial case of the clique-finding problem is finding a triangle in a graph, or equivalently determining whether the graph is triangle-free.