Clique (graph theory)
Encyclopedia
In the mathematical
area of graph theory
, a clique in an undirected graph is a subset of its vertices
such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science
: finding whether there is a clique of a given size in a graph
(the clique problem
) is NP-complete
, but despite this hardness result many algorithms for finding cliques have been studied.
Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory
by , the term "clique" comes from , who used complete subgraphs in social network
s to model clique
s of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioinformatics
.
C ⊆ V, such that for every two vertices in C, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by C is complete
(in some cases, the term clique may also refer to the subgraph).
A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique.
A maximum clique is a clique of the largest possible size in a given graph. The clique number ω(G) of a graph G is the number of vertices in a maximum clique in G. The intersection number
of G is the smallest number of cliques that together cover all edges of G.
The opposite of a clique is an independent set
, in the sense that every clique corresponds to an independent set in the complement graph
. The clique cover
problem concerns finding as few cliques as possible that include every vertex in the graph. A related concept is a biclique, a complete bipartite subgraph
. The bipartite dimension
of a graph is the minimum number of bicliques needed to cover all the edges of the graph.
Several important classes of graphs may be defined by their cliques:
Additionally, many other mathematical constructions involve cliques in graphs. Among them,
Closely related concepts to complete subgraphs are subdivisions of complete graphs and complete graph minors. In particular, Kuratowski's theorem and Wagner's theorem characterize planar graph
s by forbidden complete and complete bipartite
subdivisions and minors, respectively.
, the clique problem
is the computational problem of finding a maximum clique, or all cliques, in a given graph. It is NP-complete
, one of Karp's 21 NP-complete problems
. It is also fixed-parameter intractable
, and hard to approximate
. Nevertheless, many algorithm
s for computing cliques have been developed, either running in exponential time (such as the Bron–Kerbosch algorithm
) or specialized to graph families such as planar graph
s or perfect graph
s for which the problem can be solved in polynomial time.
s (groups of people who all know each other) in social network
s. For continued efforts to model social cliques graph-theoretically, see e.g. , , and .
Many different problems from bioinformatics
have been modeled using cliques.
For instance, model the problem of clustering gene expression
data as one of finding the minimum number of changes needed to transform a graph describing the data into a graph formed as the disjoint union of cliques; discuss a similar biclustering
problem for expression data in which the clusters are required be cliques. uses cliques to model ecological niche
s in food webs
. describe the problem of inferring evolutionary trees as one of finding maximum cliques in a graph that has as its vertices characteristics of the species, where two vertices share an edge if there exists a perfect phylogeny
combining those two characters. model protein structure prediction
as a problem of finding cliques in a graph whose vertices represent positions of subunits of the protein. And by searching for cliques in a protein-protein interaction
network, found clusters of proteins that interact closely with each other and have few interactions with proteins outside the cluster. Power graph analysis
is a method for simplifying complex biological networks by finding cliques and related structures in these networks.
In electrical engineering
, uses cliques to analyze communications networks, and use them to design efficient circuits for computing partially-specified Boolean functions. Cliques have also been used in automatic test pattern generation
: a large clique in an incompatibility graph of possible faults provides a lower bound on the size of a test set. describe an application of cliques in finding a hierarchical partition of an electronic circuit into smaller subunits.
In chemistry
, use cliques to describe chemicals in a chemical database
that have a high degree of similarity with a target structure. use cliques to model the positions in which two chemicals will bind to each other.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
area of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a clique in an undirected graph is a subset of its vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
: finding whether there is a clique of a given size in a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
(the clique problem
Clique problem
In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
) is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, but despite this hardness result many algorithms for finding cliques have been studied.
Although the study of complete subgraphs goes back at least to the graph-theoretic reformulation of Ramsey theory
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...
by , the term "clique" comes from , who used complete subgraphs in social network
Social network
A social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...
s to model clique
Clique
A clique is an exclusive group of people who share common interests, views, purposes, patterns of behavior, or ethnicity. A clique as a reference group can be either normative or comparative. Membership in a clique is typically exclusive, and qualifications for membership may be social or...
s of people; that is, groups of people all of whom know each other. Cliques have many other applications in the sciences and particularly in bioinformatics
Bioinformatics
Bioinformatics is the application of computer science and information technology to the field of biology and medicine. Bioinformatics deals with algorithms, databases and information systems, web technologies, artificial intelligence and soft computing, information and computation theory, software...
.
Definitions
A clique in an undirected graph G = (V, E) is a subset of the vertex setVertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
C ⊆ V, such that for every two vertices in C, there exists an edge connecting the two. This is equivalent to saying that the subgraph induced by C is complete
Complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
(in some cases, the term clique may also refer to the subgraph).
A maximal clique is a clique that cannot be extended by including one more adjacent vertex, that is, a clique which does not exist exclusively within the vertex set of a larger clique.
A maximum clique is a clique of the largest possible size in a given graph. The clique number ω(G) of a graph G is the number of vertices in a maximum clique in G. The intersection number
Intersection number (graph theory)
In the mathematical field of graph theory, the intersection number of a graph is the smallest number of elements in a representation of as an intersection graph of finite sets...
of G is the smallest number of cliques that together cover all edges of G.
The opposite of a clique is an independent set
Independent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
, in the sense that every clique corresponds to an independent set in the complement graph
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
. The clique cover
Clique cover
In computational complexity theory, finding a minimum clique cover is a graph-theoretical NP-complete problem. The problem was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems"....
problem concerns finding as few cliques as possible that include every vertex in the graph. A related concept is a biclique, a complete bipartite subgraph
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
. The bipartite dimension
Bipartite dimension
In the mathematical field of graph theory, the bipartite dimension of a graph G = is the minimum number of bicliques, that is, complete bipartite subgraphs, needed to cover all edges in E. A collection of bicliques covering all edges in G is called a biclique edge cover, or sometimes...
of a graph is the minimum number of bicliques needed to cover all the edges of the graph.
Mathematics
Mathematical results concerning cliques include the following.- Turán's theoremTurán's theoremIn graph theory, Turán's theorem is a result on the number of edges in a Kr+1-free graph.An n-vertex graph that does not contain any -vertex clique may be formed by partitioning the set of vertices into r parts of equal or nearly-equal size, and connecting two vertices by an edge whenever they...
gives a lower bound on the size of a clique in dense graphDense graphIn mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph...
s. If a graph has sufficiently many edges, it must contain a large clique. For instance, every graph with more than
edges must contain a three-vertex clique. - Ramsey's theoremRamsey's theoremIn combinatorics, Ramsey's theorem states that in any colouring of the edges of a sufficiently large complete graph, one will find monochromatic complete subgraphs...
states that every graph or its complement graphComplement graphIn graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
contains a clique with at least a logarithmic number of vertices. - According to a result of , a graph with 3n vertices can have at most 3n maximal cliques. The graphs meeting this bound are the Moon–Moser graphs K3,3,..., a special case of the Turán graphTurán graphThe Turán graph T is a graph formed by partitioning a set of n vertices into r subsets, with sizes as equal as possible, and connecting two vertices by an edge whenever they belong to different subsets. The graph will have subsets of size \lceil n/r\rceil, and r- subsets of size \lfloor n/r\rfloor...
s arising as the extremal cases in Turán's theorem. - Hadwiger's conjectureHadwiger conjecture (graph theory)In graph theory, the Hadwiger conjecture states that, if all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph...
, still unproven, relates the size of the largest clique minor in a graph to its chromatic number. - The Erdős–Faber–Lovász conjectureErdos–Faber–Lovász conjectureIn graph theory, the Erdős–Faber–Lovász conjecture is an unsolved problem about graph coloring, named after Paul Erdős, Vance Faber, and László Lovász, who formulated it in 1972...
is another unproven statement relating graph coloring to cliques.
Several important classes of graphs may be defined by their cliques:
- A chordal graphChordal graphIn the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
is a graph whose vertices can be ordered into a perfect elimination ordering, an ordering such that the neighbors of each vertex v that come later than v in the ordering form a clique. - A cographCographIn graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union...
is a graph all of whose induced subgraphs have the property that any maximal clique intersects any maximal independent setMaximal independent setIn graph theory, a maximal independent set or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S...
in a single vertex. - An interval graphInterval graphIn graph theory, an interval graph is the intersection graph of a multiset of intervals on the real line. It has one vertex for each interval in the set, and an edge between every pair of vertices corresponding to intervals that intersect.-Definition:...
is a graph whose maximal cliques can be ordered in such a way that, for each vertex v, the cliques containing v are consecutive in the ordering. - A line graphLine graphIn graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...
is a graph whose edges can be covered by edge-disjoint cliques in such a way that each vertex belongs to exactly two of the cliques in the cover. - A perfect graphPerfect graphIn graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....
is a graph in which the clique number equals the chromatic number in every induced subgraph. - A split graphSplit graphIn graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set...
is a graph in which some clique contains at least one endpoint of every edge. - A triangle-free graphTriangle-free graphIn the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally...
is a graph that has no cliques other than its vertices and edges.
Additionally, many other mathematical constructions involve cliques in graphs. Among them,
- The clique complexClique complexClique complexes, flag complexes, and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.-Clique complex:...
of a graph G is an abstract simplicial complexAbstract simplicial complexIn mathematics, an abstract simplicial complex is a purely combinatorial description of the geometric notion of a simplicial complex, consisting of a family of finite sets closed under the operation of taking subsets...
X(G) with a simplex for every clique in G - A simplex graphSimplex graphIn graph theory, a branch of mathematics, the simplex graph κ of an undirected graph G is itself a graph, with one node for each clique in G...
is an undirected graph κ(G) with a vertex for every clique in a graph G and an edge connecting two cliques that differ by a single vertex. It is an example of median graphMedian graphIn mathematics, and more specifically graph theory, a median graph is an undirected graph in which any three vertices a, b, and c have a unique median: a vertex m that belongs to shortest paths between any two of a, b, and c.The concept of median graphs has long been studied, for instance by or ...
, and is associated with a median algebraMedian algebraIn mathematics, a median algebra is a set with a ternary operation < x,y,z > satisfying a set of axioms which generalise the notion of median or majority function, as a Boolean function.The axioms are# < x,y,y > = y...
on the cliques of a graph: the median m(A,B,C) of three cliques A, B, and C is the clique whose vertices belong to at least two of the cliques A, B, and C. - The clique-sumClique-sumIn graph theory, a branch of mathematics, a clique-sum is a way of combining two graphs by gluing them together at a clique, analogous to the connected sum operation in topology...
is a method for combining two graphs by merging them along a shared clique. - Clique-widthClique-widthIn graph theory, the clique-width of a graph G is the minimum number of labels needed to construct G by means of the following 4 operations :#Creation of a new vertex v with label i...
is a notion of the complexity of a graph in terms of the minimum number of distinct vertex labels needed to build up the graph from disjoint unions, relabeling operations, and operations that connect all pairs of vertices with given labels. The graphs with clique-width one are exactly the disjoint unions of cliques. - The intersection numberIntersection number (graph theory)In the mathematical field of graph theory, the intersection number of a graph is the smallest number of elements in a representation of as an intersection graph of finite sets...
of a graph is the minimum number of cliques needed to cover all the graph's edges.
Closely related concepts to complete subgraphs are subdivisions of complete graphs and complete graph minors. In particular, Kuratowski's theorem and Wagner's theorem characterize planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s by forbidden complete and complete bipartite
Complete bipartite graph
In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
subdivisions and minors, respectively.
Computer science
In computer scienceComputer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the clique problem
Clique problem
In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....
is the computational problem of finding a maximum clique, or all cliques, in a given graph. It is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, one of Karp's 21 NP-complete problems
Karp's 21 NP-complete problems
One of the most important results in computational complexity theory was Stephen Cook's 1971 demonstration of the first NP-complete problem, the boolean satisfiability problem...
. It is also fixed-parameter intractable
Parameterized complexity
Parameterized complexity is a branch of computational complexity theory in computer science that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input. The complexity of a problem is then measured as a function in those...
, and hard to approximate
Hardness of approximation
In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. It complements the study of approximation algorithms by proving, for certain problems, a limit on the factors with which their solution can...
. Nevertheless, many algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s for computing cliques have been developed, either running in exponential time (such as the Bron–Kerbosch algorithm
Bron–Kerbosch algorithm
In computer science, the Bron–Kerbosch algorithm is an algorithm for finding maximal cliques in an undirected graph. That is, it lists all subsets of vertices with the two properties that each pair of vertices in one of the listed subsets is connected by an edge, and no listed subset can have any...
) or specialized to graph families such as planar graph
Planar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
s or perfect graph
Perfect graph
In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....
s for which the problem can be solved in polynomial time.
Applications
The word "clique", in its graph-theoretic usage, arose from the work of , who used complete subgraphs to model cliqueClique
A clique is an exclusive group of people who share common interests, views, purposes, patterns of behavior, or ethnicity. A clique as a reference group can be either normative or comparative. Membership in a clique is typically exclusive, and qualifications for membership may be social or...
s (groups of people who all know each other) in social network
Social network
A social network is a social structure made up of individuals called "nodes", which are tied by one or more specific types of interdependency, such as friendship, kinship, common interest, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.Social...
s. For continued efforts to model social cliques graph-theoretically, see e.g. , , and .
Many different problems from bioinformatics
Bioinformatics
Bioinformatics is the application of computer science and information technology to the field of biology and medicine. Bioinformatics deals with algorithms, databases and information systems, web technologies, artificial intelligence and soft computing, information and computation theory, software...
have been modeled using cliques.
For instance, model the problem of clustering gene expression
Gene expression
Gene expression is the process by which information from a gene is used in the synthesis of a functional gene product. These products are often proteins, but in non-protein coding genes such as ribosomal RNA , transfer RNA or small nuclear RNA genes, the product is a functional RNA...
data as one of finding the minimum number of changes needed to transform a graph describing the data into a graph formed as the disjoint union of cliques; discuss a similar biclustering
Biclustering
Biclustering, co-clustering, or two-mode clustering is a data mining technique which allows simultaneous clustering of the rows and columns of a matrix....
problem for expression data in which the clusters are required be cliques. uses cliques to model ecological niche
Ecological niche
In ecology, a niche is a term describing the relational position of a species or population in its ecosystem to each other; e.g. a dolphin could potentially be in another ecological niche from one that travels in a different pod if the members of these pods utilize significantly different food...
s in food webs
Food chain
A food web depicts feeding connections in an ecological community. Ecologists can broadly lump all life forms into one of two categories called trophic levels: 1) the autotrophs, and 2) the heterotrophs...
. describe the problem of inferring evolutionary trees as one of finding maximum cliques in a graph that has as its vertices characteristics of the species, where two vertices share an edge if there exists a perfect phylogeny
Perfect phylogeny
Perfect phylogeny is a term used in computational phylogenetics to denote a phylogenetic tree in which all internal nodes may be labeled as such that all characters evolve down the tree without homoplasy. That is, characteristics do not hold to evolutionary convergence, and do not have analogous...
combining those two characters. model protein structure prediction
Protein structure prediction
Protein structure prediction is the prediction of the three-dimensional structure of a protein from its amino acid sequence — that is, the prediction of its secondary, tertiary, and quaternary structure from its primary structure. Structure prediction is fundamentally different from the inverse...
as a problem of finding cliques in a graph whose vertices represent positions of subunits of the protein. And by searching for cliques in a protein-protein interaction
Protein-protein interaction
Protein–protein interactions occur when two or more proteins bind together, often to carry out their biological function. Many of the most important molecular processes in the cell such as DNA replication are carried out by large molecular machines that are built from a large number of protein...
network, found clusters of proteins that interact closely with each other and have few interactions with proteins outside the cluster. Power graph analysis
Power graph analysis
In computational biology, power graph analysis is a method for the analysis andrepresentation of complex networks. Power graph analysis is the computation, analysis and visual representation of a power graph from a graphs ....
is a method for simplifying complex biological networks by finding cliques and related structures in these networks.
In electrical engineering
Electrical engineering
Electrical engineering is a field of engineering that generally deals with the study and application of electricity, electronics and electromagnetism. The field first became an identifiable occupation in the late nineteenth century after commercialization of the electric telegraph and electrical...
, uses cliques to analyze communications networks, and use them to design efficient circuits for computing partially-specified Boolean functions. Cliques have also been used in automatic test pattern generation
Automatic test pattern generation
ATPG is an electronic design automation method/technology used to find an input sequence that, when applied to a digital circuit, enables automatic test equipment to distinguish between the correct circuit behavior and the faulty circuit...
: a large clique in an incompatibility graph of possible faults provides a lower bound on the size of a test set. describe an application of cliques in finding a hierarchical partition of an electronic circuit into smaller subunits.
In chemistry
Chemistry
Chemistry is the science of matter, especially its chemical reactions, but also its composition, structure and properties. Chemistry is concerned with atoms and their interactions with other atoms, and particularly with the properties of chemical bonds....
, use cliques to describe chemicals in a chemical database
Chemical database
A chemical database is a database specifically designed to store chemical information. This information is about chemical and crystal structures, spectra, reactions and syntheses, and thermophysical data.- Chemical structures :...
that have a high degree of similarity with a target structure. use cliques to model the positions in which two chemicals will bind to each other.