Clique (graph theory) of an undirected graph

A clique of an undirected graph is a subset of its vertices, any two of which are joined by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions with graphs. Cliques are also studied in computer science — the problem of determining whether a clique of a given size exists in a graph (the clique problem) is NP-complete. Despite this difficulty, many algorithms for finding cliques are studied.

Although the study of complete subgraphs began with the formulation of Ramsey's theorem in graph-theoretic terms by Erdős and Szekeres . The term «clique» came from the work of Luce and Perry , who used complete subgraphs in the study of social networks to model cliques of people, that is, groups of people acquainted with each other . Cliques have many other applications in science, and, in particular, in bioinformatics.

Definitions

A clique in an undirected graph is a subset of vertices , such that for any two vertices in there exists an edge joining them. This is equivalent to the statement that the subgraph induced by , is complete.

A maximal clique, or a clique that is maximal with respect to inclusion — is a clique that cannot be extended by adding vertices to it. In other words, in the given graph there is no clique of larger size in which it is contained.

A maximum clique, or a clique that is maximum in size — is a clique of maximum size for the given graph.

The clique number of the graph — is the number of vertices in the maximum clique of the graph . The intersection number of the graph — is the smallest number of cliques that together cover all edges of the graph .

The notion opposite to a clique — is an independent set, in the sense that each clique corresponds to an independent set in the complement graph. The clique cover problem consists of finding as few cliques as possible that contain all vertices of the graph.

A related term — is a biclique, a complete bipartite subgraph. The bipartite dimension of a graph — is the minimum number of bicliques needed to cover all edges of the graph.

Mathematics

Mathematical results concerning cliques include the following.

• Turán's theorem gives a lower bound on the number of cliques in dense graphs. If a graph has sufficiently many edges, it must contain a clique. For example, any graph with vertices and more than edges must have a clique of three vertices.
• Ramsey's theorem states that any graph or its complement contains a clique with at least a logarithmic number of vertices.
• According to the results of Moon and Moser , a graph with vertices can contain at most maximal cliques. The graphs satisfying this bound — are the Moon — Moser graphs — a special case of Turán graphs, arising as the extremal case of Turán's theorem.
• Hadwiger's conjecture, which remains unproved, relates the size of the largest clique minor in a graph (its Hadwiger number) to its chromatic number.
• The Erdős — Faber — Lovász conjecture — is another unproved statement concerning the relation of graph coloring to cliques.

Some important classes of graphs can be defined by their cliques:

• A chordal graph — is a graph whose vertices can be ordered in a perfect elimination ordering; an ordering in which the neighbors of each vertex come after the vertex .
• A cograph — is a graph all of whose induced subgraphs have the property that any maximum clique intersects any maximum independent set in a single vertex.
• An interval graph — is a graph whose maximal cliques can be ordered so that for any vertex , the cliques containing , come consecutively.
• A line graph — is a graph whose edges can be covered by cliques without common edges, where each vertex belongs to exactly two cliques.
• A perfect graph — is a graph in which the clique number equals the chromatic number in every induced subgraph.
• A split graph — is a graph in which some set of cliques contains at least one vertex from each edge.
• A triangle-free graph — is a graph in which there are no cliques other than vertices and edges.

In addition, many other mathematical constructions involve cliques of graphs. Among them:

• The clique complex of the graph — is an abstract simplicial complex with a simplex for each clique in ;
• The simplex graph — is an undirected graph with a vertex for each clique in the graph and edges joining two cliques that differ by one vertex. This graph is an example of a median graph and is connected with the median algebra on the cliques of the graph — the median of three cliques , and — is the clique whose vertices belong to at least two of the cliques , and ;
• The clique sum — is a method of combining two graphs by merging them along a clique;
• Clique-width — is a complexity category of graphs in terms of the minimum number of distinct vertex labels needed to build the graph from disjoint sets using labeling operations and operations joining all pairs of vertices with the same labels. Graphs of clique-width one — are exactly disjoint sets of cliques;
• The intersection number of a graph — is the minimum number of cliques needed to cover all edges of the graph.

A concept close to complete subgraphs — is partitions of graphs into complete subgraphs and complete minors of a graph. In particular, Kuratowski's theorem and Wagner's theorem characterize planar graphs by forbidding complete and complete bipartite subgraphs and minors, respectively.

Computer science: the clique problem

In computer science the clique problem — is the computational problem of finding the maximum clique or cliques in a given graph. The problem is NP-complete, one of Karp's 21 NP-complete problems . It is also hard for parametric approximation and hard to approximate. Nevertheless, many algorithms have been developed for working with cliques, running either in exponential time (such as the Bron — Kerbosch algorithm), or specializing in families of graphs, such as planar graphs or perfect graphs, for which the problem can be solved in polynomial time.

Free software for finding a maximum clique

Below is a list of freely distributed software for finding a maximum clique.

The clique problem belongs to the class of NP-complete problems in the field of graph theory. It was first formulated in 1972 by Richard Karp.

A graph with a clique of size 3.

A clique in an undirected graph is a subset of vertices, any two of which are joined by an edge of the graph. In other words, it is a complete subgraph of the original graph. The size of a clique is defined as the number of vertices in it. The clique problem exists in two variants: in the decision problem one is required to determine whether a clique of size k exists in a given graph G, whereas in the computational variant one is required to find a clique of maximum size in a given graph G.

NP-completeness

The NP-completeness of the clique problem follows from the NP-completeness of the independent vertex set problem. It is easy to show that a necessary and sufficient condition for the existence of a clique of size k is the presence of an independent set of size at least k in the complement of the graph. This is obvious, since the completeness of a subgraph means that its complement contains no edge.

Another proof of NP-completeness can be found in the book «Introduction to Algorithms».

Algorithms

As for other NP-complete problems, an efficient algorithm for finding a clique of a given size has not been found at present. An exhaustive search of all possible subgraphs of size k with a check of whether at least one of them is complete — is inefficient, since the total number of such subgraphs in a graph with v vertices equals the binomial coefficient

Another algorithm works as follows: two cliques of size n and m are «glued» into a larger clique of size n+m, where a clique of size 1 is taken to be a single vertex of the graph. The algorithm terminates as soon as no more merges can be performed. The running time of this algorithm is linear, but it is heuristic, since it does not always lead to finding a clique of maximum size. As an example of an unsuccessful termination one can cite the case where the vertices belonging to the maximum clique turn out to be separated and located in cliques of smaller size, and the latter can no longer be «glued» together.

König's theorem. In a bipartite graph the size of the maximum matching equals the size of the minimum vertex cover.

From König's theorem it follows that

the size of the maximum clique =

the size of the maximum independent set in the complement graph =

the number of vertices of the graph – the size of the minimum vertex cover =

the number of vertices of the graph – the size of the maximum matching in the complement graph

Example

Let us consider the second example. The size of the maximum clique of the graph equals 4. The size of the maximum independent set in the complement graph equals 4.

Applications

Many different bioinformatics problems have been modeled using cliques. For example, Ben-Dor, Shamir and Yakhini^[10] modeled the problem of partitioning gene expression into groups as the problem of finding the minimum number of changes needed to transform a data graph into a graph formed by disjoint sets of cliques. Tanay, Sharan and Shamir^[11] discuss a similar problem of biclustering gene-expression data, in which the clusters must be cliques. Sugihara used cliques to model ecological niches in food chains. Day and Sankoff describe the problem of describing evolutionary trees as the problem of finding maximum cliques in a graph in which the vertices represent characteristics, and two vertices are joined by an edge if there exists a perfect phylogeny , combining these two characteristics. Samudrala and Moult modeled protein-structure prediction as the problem of finding cliques in a graph whose vertices represent positions of parts of the protein, and by searching for cliques in a protein-protein interaction network , Spirin and Mirny found clusters of proteins that interact closely with each other and interact weakly outside the cluster. Graph power analysis — is a method of simplifying complex biological systems by finding cliques and related structures in these systems.

In electrical engineering, Prihar used cliques to analyze communication networks, and Paull and Unger used them to design efficient circuits for computing partially defined Boolean functions. Cliques are also used in automatic test-pattern generation — a large clique in the incompatibility graph of possible faults gives a lower bound on the set of tests . Kong and Smith describe the application of cliques to finding hierarchical structures in electrical circuits.

In chemistry, Rhodes et al. used cliques to describe chemical compounds in a chemical database , having a high degree of similarity. Kuhl, Crippen and Friesen used cliques to model the positions at which two chemical compounds bind to each other.

See also

• Flag complex