Hubbry Logo
Clique (graph theory)Clique (graph theory)Main
Open search
Clique (graph theory)
Community hub
Clique (graph theory)
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Clique (graph theory)
Clique (graph theory)
Clique (graph theory)
View on Wikipedia
from Wikipedia
A graph with
  • 23 × 1-vertex cliques (the vertices),
  • 42 × 2-vertex cliques (the edges),
  • 19 × 3-vertex cliques (light and dark blue triangles), and
  • 2 × 4-vertex cliques (dark blue areas).
The 11 light blue triangles form maximal cliques. The two dark blue 4-cliques are both maximum and maximal, and the clique number of the graph is 4.

In graph theory, a clique (/ˈkliːk/ or /ˈklɪk/) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. 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: the task of 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 Erdős & Szekeres (1935),[1] the term clique comes from Luce & Perry (1949), who used complete subgraphs in social networks to model cliques 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.

Definitions

[edit]

A clique, C, in an undirected graph G = (V, E) is a subset of the vertices, C ⊆ V, such that every two distinct vertices are adjacent. This is equivalent to the condition that the induced subgraph of G induced by C is a complete graph. In some cases, the term clique may also refer to the subgraph directly.

A maximal clique is a clique that is not a subset of any larger clique. Some authors define cliques in a way that requires them to be maximal, and use other terminology for complete subgraphs that are not maximal.

A maximum clique of a graph, G, is a clique, such that there is no clique with more vertices. Moreover, 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 clique cover number of a graph G is the smallest number of cliques of G whose union covers the set of vertices V of the graph.

A maximum clique transversal of a graph is a subset of vertices with the property that each maximum clique of the graph contains at least one vertex in the subset.[2]

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.

Mathematics

[edit]

Mathematical results concerning cliques include the following.

Several important classes of graphs may be defined or characterized by their cliques:

  • A cluster graph is a graph whose connected components are cliques.
  • A block graph is a graph whose biconnected components are cliques.
  • A chordal graph 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 cograph is a graph all of whose induced subgraphs have the property that any maximal clique intersects any maximal independent set in a single vertex.
  • An interval graph 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 graph 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 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 clique contains at least one endpoint of every edge.
  • A triangle-free graph 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 complex of a graph G is an abstract simplicial complex X(G) with a simplex for every clique in G
  • A simplex graph 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 graph, and is associated with a median algebra 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.[5]
  • The clique-sum is a method for combining two graphs by merging them along a shared clique.
  • Clique-width 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 number of a graph is the minimum number of cliques needed to cover all the graph's edges.
  • The clique graph of a graph is the intersection graph of its maximal cliques.

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 graphs by forbidden complete and complete bipartite subdivisions and minors, respectively.

Computer science

[edit]
Main article: Clique problem

In computer science, 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.[6] It is also fixed-parameter intractable, and hard to approximate. Nevertheless, many algorithms 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 graphs or perfect graphs for which the problem can be solved in polynomial time.

Applications

[edit]

The word "clique", in its graph-theoretic usage, arose from the work of Luce & Perry (1949), who used complete subgraphs to model cliques (groups of people who all know each other) in social networks. The same definition was used by Festinger (1949) in an article using less technical terms. Both works deal with uncovering cliques in a social network using matrices. For continued efforts to model social cliques graph-theoretically, see e.g. Alba (1973), Peay (1974), and Doreian & Woodard (1994).

Many different problems from bioinformatics have been modeled using cliques. For instance, Ben-Dor, Shamir & Yakhini (1999) 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; Tanay, Sharan & Shamir (2002) discuss a similar biclustering problem for expression data in which the clusters are required to be cliques. Sugihara (1984) uses cliques to model ecological niches in food webs. Day & Sankoff (1986) 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. Samudrala & Moult (1998) 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, Spirin & Mirny (2003) 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, Prihar (1956) uses cliques to analyze communications networks, and Paull & Unger (1959) 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.[7] Cong & Smith (1993) describe an application of cliques in finding a hierarchical partition of an electronic circuit into smaller subunits.

In chemistry, Rhodes et al. (2003) use cliques to describe chemicals in a chemical database that have a high degree of similarity with a target structure. Kuhl, Crippen & Friesen (1983) use cliques to model the positions in which two chemicals will bind to each other.

See also

[edit]

Notes

[edit]

References

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Clique (graph theory)

View on Grokipedia
from Grokipedia
In , a clique is a of vertices in an undirected graph such that every two distinct vertices in the are adjacent, meaning the on those vertices is (isomorphic to a complete graph KkK_k for some kk). Single vertices and edges qualify as cliques of size 1 and 2, respectively, and the concept extends to larger complete subgraphs where all possible edges are present. A maximal clique is one that cannot be extended by including an additional adjacent vertex, while a maximum clique is a clique of largest possible size in the graph, denoted by the clique number ω(G)\omega(G). The clique number provides a key measure of graph , as it represents the maximum degree of "complete connectivity" within the graph; for example, in the complete graph KnK_n, ω(Kn)=n\omega(K_n) = n. Cliques are intimately related to independent sets via the graph complement: a set of vertices forms a in GG it forms an independent set (no edges between vertices) in the complement graph GcG^c, leading to the identity ω(G)=α(Gc)\omega(G) = \alpha(G^c), where α(G)\alpha(G) is the number. The problem of finding a maximum clique in a graph, known as the maximum (MCP), is a fundamental computational challenge and one of Karp's 21 original NP-complete problems, making it NP-hard in general. Exact algorithms for MCP often rely on branch-and-bound techniques or , but they scale poorly for large graphs due to the in possible subsets; algorithms and heuristics, such as greedy methods or relaxations, are commonly used in practice. In complexity theory, the decision version—determining if a graph contains a of size at least kk—is NP-complete, with reductions from problems like 3-SAT highlighting its hardness. Cliques play a central role in various applications, including social network analysis where they represent groups of mutually acquainted individuals, such as friend circles on platforms like . In bioinformatics, identifying cliques in protein-protein interaction graphs helps predict protein complexes or functional modules. They also arise in optimization problems like (where ω(G)\omega(G) bounds the chromatic number from below) and scheduling in interval graphs, as well as in for constructing error-correcting codes. Ramsey theory further underscores their ubiquity, guaranteeing that sufficiently large graphs contain either large cliques or large independent sets, with Ramsey numbers R(k,l)R(k,l) quantifying these thresholds.

Fundamentals

Definition

In , the term "" originates from the 1949 work of Luce and Perry, who applied complete subgraphs to model tightly knit groups in social networks represented as graphs. A in an undirected simple graph G=(V,E)G = (V, E) is a S⊆VS \subseteq V of vertices such that every pair of distinct vertices in SS is connected by an edge in EE. Equivalently, the G[S]G[S] on the vertex set SS is a , meaning it contains all possible edges between vertices in SS. A of size rr (i.e., with ∣S∣=r|S| = r) is called an rr-, and the complete graph on rr vertices, denoted KrK_r, provides the standard isomorphic form for such a structure. This definition emphasizes the induced nature of the clique, as the subgraph must include exactly the edges present in GG between the vertices in SS, with no missing edges within SS but potentially ignoring edges outside SS. In contrast, cliques differ from related structures like independent sets; specifically, in the complement graph Gˉ\bar{G} (where edges exist between non-adjacent vertices of GG), a clique in GG corresponds precisely to an independent set in Gˉ\bar{G}, and vice versa.

Examples

A basic example of a clique is the K2K_2, which consists of two vertices connected by an edge; this forms the smallest non-trivial . In a PnP_n with n≥3n \geq 3, such as a of vertices connected sequentially, each individual edge induces a K2K_2 , but no larger cliques exist due to the absence of additional edges between non-consecutive vertices. A prominent example is the , denoted K3K_3, where three vertices are pairwise adjacent, forming a complete subgraph on three vertices. This structure appears frequently in as the prototypical of size three. For a non-trivial case illustrating limited clique size, the , a well-known 3-regular graph with 10 vertices, has a maximum of size 2 and contains no triangles (K3K_3). To aid visualization, consider the C5C_5, which consists of five vertices connected in a closed loop forming a ; in such a , no three vertices are all mutually adjacent, so the largest is K2K_2, confirming the absence of K3K_3. Similarly, in a Km,nK_{m,n}, depicted as two of vertices with all possible edges between the sets but none within, the maximum clique size is 2, as any three vertices would include at least two from the same partition lacking an edge. Trivial edge cases include the single-vertex graph, which is the clique K1K_1 with no edges, and the empty graph with zero vertices, which contains no non-empty cliques.

Properties

Maximal and Maximum Cliques

In graph theory, a maximal clique is a clique that cannot be extended by adding another vertex while preserving the complete subgraph property, meaning no vertex outside the clique is adjacent to every vertex within it. This implies that a maximal clique is not a proper subset of any larger clique in the graph. Every graph contains at least one maximal clique; for instance, in an empty graph with no edges, each single vertex forms a maximal clique of size one, as no extensions are possible. A maximum clique, in contrast, is a clique of the largest possible size in the graph, denoted by its cardinality, though such cliques are not necessarily unique. For example, in a complete graph KnK_n, the entire vertex set forms the unique maximum clique of size nn. Every maximum clique is inherently maximal, since enlarging it further would contradict its maximum size, but the converse does not hold: a graph may contain multiple maximal cliques of different sizes that are not maximum. Consider a graph consisting of a triangle (clique of size 3) connected to a disjoint edge (clique of size 2); here, the triangle is a maximum clique, the edge is a maximal clique of smaller size, and any isolated vertices would form additional maximal cliques of size 1. To determine if a given is maximal, one checks extendability by examining each vertex outside the clique to see if it is adjacent to all vertices in the clique; if no such vertex exists, the clique is maximal. This vertex-by-vertex adjacency verification highlights the local nature of maximality in the graph's structure. Maximal cliques play a key role in graph decomposition, such as in clique partitions, which cover the entire vertex set with disjoint cliques, partitioning the graph into non-overlapping complete subgraphs. The minimum number of such cliques in a partition is known as the clique partition number.

Clique Number

The clique number of a graph GG, denoted ω(G)\omega(G), is the number of vertices in a maximum in GG. Equivalently, it is the largest integer rr such that the KrK_r is a subgraph of GG. For an edgeless graph on nn vertices, ω(G)=1\omega(G) = 1, as the largest consists of a single isolated vertex. In contrast, for the KnK_n on nn vertices, ω(G)=n\omega(G) = n, since the entire vertex set forms a . There is no closed-form formula to compute ω(G)\omega(G) for arbitrary graphs in general. In certain special graph classes, the clique number takes on simple values. For the complete bipartite graph Km,nK_{m,n}, ω(G)=2\omega(G) = 2, as bipartite graphs contain no odd cycles and thus no triangles. Similarly, for any , which is a connected acyclic graph and hence bipartite, ω(G)=2\omega(G) = 2. For s, ω(G)≤4\omega(G) \leq 4; this follows from the fact that K5K_5 is non-planar and thus cannot appear as a subgraph in any planar graph. The clique number relates to other graph invariants, notably the chromatic number χ(G)\chi(G), which satisfies χ(G)≥ω(G)\chi(G) \geq \omega(G) for any graph GG, since a clique of size rr requires at least rr colors in a proper vertex coloring. Equality holds, χ(G)=ω(G)\chi(G) = \omega(G), for every of a . Additionally, the clique number of the G‾\overline{G} equals the number α(G)\alpha(G) of GG.

Mathematical Theory

Extremal Graph Theory

investigates the maximum number of edges in a graph that avoids certain subgraphs, with playing a central role as forbidden complete subgraphs KrK_r. A key question is determining the largest KrK_r-free graph on nn vertices, measured by the Turán number \ex(n,Kr)\ex(n, K_r), which denotes the maximum edges in such a graph. This area originated with problems on avoiding small , evolving into broad theorems bounding clique sizes through edge constraints. In 1941, Paul Turán formulated a seminal result addressing the maximum edges in an nn-vertex KrK_r-free graph, motivated by extremal problems in combinatorics during his internment in a labor camp. Turán's theorem states that \ex(n,Kr)\ex(n, K_r) is achieved by the Turán graph T(n,r−1)T(n, r-1), the complete balanced (r−1)(r-1)-partite graph on nn vertices with parts as equal as possible in size. This construction partitions the vertices into r−1r-1 independent sets of sizes differing by at most 1, connecting all edges between different sets but none within. The theorem asserts that any KrK_r-free graph on nn vertices has at most as many edges as T(n,r−1)T(n, r-1), and T(n,r−1)T(n, r-1) itself is KrK_r-free. The number of edges in T(n,r−1)T(n, r-1) is given by \ex(n,Kr)=(1−1r−1)n22,\ex(n, K_r) = \left(1 - \frac{1}{r-1}\right) \frac{n^2}{2}, approximately, with the exact value t(n,r−1)=(n2)−s(k+12)−((r−1)−s)(k2)t(n, r-1) = \binom{n}{2} - s \binom{k+1}{2} - ((r-1)-s) \binom{k}{2}, where k=⌊n/(r−1)⌋k = \lfloor n/(r-1) \rfloor and s=nmod  (r−1)s = n \mod (r-1), so ss parts have size k+1k+1 and r−1−sr-1 - s parts have size kk. To derive this, compute the edges as the sum over all pairs of parts: for parts of sizes ai,aja_i, a_j (i≠ji \neq j), add aiaja_i a_j, yielding the maximized under the balanced partition constraint by the AM-QM inequality or direct calculation. This formula establishes the asymptotic 1−1/(r−1)1 - 1/(r-1) for large nn. One proof of employs Zykov symmetrization, introduced by Alexander Zykov in 1949, which iteratively transforms any KrK_r-free graph into a complete (r−1)(r-1)-partite graph without decreasing edges. The method selects non-adjacent vertices u,vu, v with maximum degrees, replaces neighbors of vv with edges from uu to those neighbors (symmetrizing by making uu dominate vv's connections), and removes vv; repeating yields a multipartite graph with at least as many edges, eventually reaching the balanced Turán graph as the unique maximum. This symmetrization preserves KrK_r-freeness and non-decreasing edges, proving the extremal construction. A prominent corollary is Mantel's theorem for r=3r=3, stating that the maximum edges in an nn-vertex triangle-free graph is ⌊n2/4⌋\lfloor n^2/4 \rfloor, achieved by the complete bipartite graph K⌊n/2⌋,⌈n/2⌉K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}, the Turán graph T(n,2)T(n,2). This 1907 result predates Turán's generalization and bounds triangle-free graphs specifically. The Erdős–Stone theorem generalizes Turán's result to arbitrary forbidden graphs HH with chromatic number χ(H)=r≥2\chi(H) = r \geq 2, asserting that \ex(n,H)=(1−1r−1+o(1))n22\ex(n, H) = \left(1 - \frac{1}{r-1} + o(1)\right) \frac{n^2}{2}, where the o(1)o(1) term vanishes as n→∞n \to \infty, and the extremal graphs approximate T(n,r−1)T(n, r-1) plus a bounded number of edges. Proved in 1946, it shows that the Turán density governs the asymptotics for any non-bipartite HH, with the error depending on the structure beyond the chromatic number.

Intersection Theorems

In , intersection theorems for cliques focus on families of cliques in a graph where every pair of cliques shares at least one vertex, providing bounds on the maximum size of such families. These results originated in extremal set theory but apply directly to cliques, as the k-cliques of the KnK_n correspond precisely to the k-subsets of the n vertices. The foundational theorem in this area is the , which quantifies the largest possible intersecting family of k-cliques under suitable conditions. The states that if n≥2kn \geq 2k and F\mathcal{F} is a family of k-subsets of an n-element set such that every two members of F\mathcal{F} intersect (i.e., F\mathcal{F} is intersecting), then ∣F∣≤(n−1k−1)|\mathcal{F}| \leq \binom{n-1}{k-1}. Equality holds if and only if F\mathcal{F} consists of all k-subsets containing a fixed element. In graph-theoretic terms, this bounds the maximum number of pairwise intersecting k-cliques in KnK_n. The theorem was proved in 1961 by , Chao Ko, and Richard Rado using a combinatorial argument involving the Kruskal–Katona theorem and shifting operations on set families. A simpler proof, due to Gyula O. H. Katona in , employs double counting on cyclic arrangements. Consider the vertices labeled 1 through n arranged in a cycle. Partition the possible k-subsets (or k-cliques) into classes based on their positions relative to the cycle: specifically, group them by whether they form a consecutive block of k elements or span across the cycle boundary. For an intersecting F\mathcal{F}, at most half of the k-subsets in each such class can be selected without violating the intersection property, leading to ∣F∣≤12(nk)|\mathcal{F}| \leq \frac{1}{2} \binom{n}{k}. For n≥2kn \geq 2k, this bound refines to (n−1k−1)\binom{n-1}{k-1} via averaging over rotations of the cycle and counting pairs of intersecting sets. Another approach uses linear : the characteristic vectors of the sets in F\mathcal{F} are considered in the over R\mathbb{R} with basis the k-subsets, and the intersection condition implies that the sum of these vectors has nonnegative entries, with the maximum norm bounded by the all-ones vector shifted to fix one coordinate, yielding the same bound. This method, popularized by Lovász and others, leverages the of the . The theorem extends to various settings relevant to graph cliques. In uniform hypergraphs, where hyperedges represent potential clique structures, variants bound intersecting families of r-uniform hyperedges that correspond to cliques in the underlying graph. A key refinement is the Hilton–Milner theorem (1967), which addresses non-trivial intersecting families—those without a common element to all sets. It states that if F\mathcal{F} is a k-uniform intersecting family on n elements with n>2kn > 2k and no common intersection, then ∣F∣≤(n−1k−1)−(n−k−1k−1)+1|\mathcal{F}| \leq \binom{n-1}{k-1} - \binom{n-k-1}{k-1} + 1, with equality for the family consisting of a fixed (k-1)-set union one additional element, plus all k-subsets containing that fixed (k-1)-set and intersecting it nontrivially. In graph terms, this gives the extremal size for families of k-cliques with pairwise nonempty intersections but no universal vertex. The proof combines the Erdős–Ko–Rado bound with a shifting argument to exclude the trivial case. These theorems find applications in , where blocks of a balanced incomplete block design (BIBD) can be viewed as cliques in the on the point set. The Erdős–Ko–Rado bound limits the size of intersecting collections of blocks, ensuring that designs with pairwise intersecting blocks (e.g., in projective planes or Steiner systems) achieve at most the starring construction size, which informs the existence and structure of such designs. For instance, in a t-(v,k,λ) design, the theorem implies bounds on t-intersecting block families, with equality often tied to derived subsystems.

Computation

Algorithms

One of the most widely used exact algorithms for enumerating all maximal s in an undirected graph is the Bron-Kerbosch algorithm, introduced in as a recursive procedure that systematically explores subsets of vertices to identify maximal cliques without duplicates. The algorithm maintains three sets: a current clique RR, a set of candidate vertices PP that can extend RR, and a set of excluded vertices XX that are neighbors of previously considered candidates but not in PP. It reports RR as a maximal clique when both PP and XX are empty, and recursively branches by selecting vertices from PP to build larger cliques while updating the sets based on adjacency. A basic version of the Bron-Kerbosch algorithm can be outlined in pseudocode as follows:

procedure BronKerbosch(R, P, X): if P is empty and X is empty: report R as a maximal clique for each vertex v in P: BronKerbosch(R ∪ {v}, P ∩ N(v), X ∩ N(v)) P ← P \ {v} X ← X ∪ {v}

procedure BronKerbosch(R, P, X): if P is empty and X is empty: report R as a maximal clique for each vertex v in P: BronKerbosch(R ∪ {v}, P ∩ N(v), X ∩ N(v)) P ← P \ {v} X ← X ∪ {v}

Here, N(v)N(v) denotes the set of neighbors of vertex vv, excluding vv itself. This version has a worst-case time complexity exponential in the graph size but performs well on sparse graphs in practice. An important improvement, the pivoting variant, reduces redundant recursions by selecting a pivot vertex uu from P∪XP \cup X and only branching on candidates in P∖N(u)P \setminus N(u), as any maximal clique containing uu will be found through other branches. This version was proposed by Tomita et al. in 2006 and significantly enhances efficiency on many real-world graphs by minimizing the number of recursive calls. For finding a single maximum clique (the largest possible clique), branch-and-bound s are commonly employed, which prune the search space using upper bounds derived from graph colorings or other relaxations. A seminal such by Östergård (2002) orders vertices by degree and uses sequential bounding to explore branches efficiently, achieving strong performance on dense graphs up to hundreds of vertices. Another exact approach reduces the maximum clique problem to (SAT) by encoding vertex selections and edge constraints as clauses, solvable via the Davis-Putnam procedure or its successors; this has been effectively used in hybrid solvers for large instances. Approximation algorithms for the maximum provide polynomial-time guarantees but with ratios far from optimal due to the problem's . A greedy coloring-based method applied to the \bar{G} colors vertices sequentially, yielding an upper bound on the chromatic number χ(\bar{G}) ≤ Δ(\bar{G}) + 1. Since the independence number α(\bar{G}) ≥ n / χ(\bar{G}), and ω(G) = α(\bar{G}), this implies a clique of size at least n / (Δ(\bar{G}) + 1) in G by taking the largest color class in \bar{G} (an independent set there, hence a clique in G). Simple greedy methods achieve approximation ratios like O(n / log n) in some analyses, but the problem cannot be approximated within n^{1-ε} for any ε > 0 unless P = NP. (SDP) relaxations, such as the Lovász ϑ(G)\vartheta(G), provide tighter bounds with ω(G)≤ϑ(G)≤χ(G‾)\omega(G) \leq \vartheta(G) \leq \chi(\overline{G}), and rounding techniques from SDP solutions yield approximate cliques; de Klerk et al. (2007) developed SDP hierarchies that improve on basic relaxations for both clique and coloring problems. Heuristic methods, suitable for very large graphs where exact solutions are infeasible, include local search algorithms that start with a small and iteratively add or swap vertices to maximize size while maintaining completeness, often repeating from random starts. A simple repeated greedy heuristic builds by sequentially adding the vertex with the highest degree in the current subgraph's neighborhood, restarting multiple times to escape local optima; this performs well on sparse networks despite lacking guarantees. Recent advances as of 2025 include quantum algorithms using Grover's search for exponential speedup in detecting on quantum hardware and to learn vertex orderings that enhance exact branch-and-bound solvers on large graphs.

Complexity

The maximum clique problem, which asks for the size of the largest in an undirected graph, is NP-hard, and its decision version—determining whether a graph contains a of size at least kk—is . This was established in one of the original demonstrations of , via a polynomial-time from the 3-SAT problem. In the reduction, for a 3-SAT with mm clauses over nn variables, a graph is constructed with $3mvertices,oneforeachliteraloccurrenceintheclauses.Anedgeisaddedbetweentwoverticesiftheybelongtodifferentclausesandrepresentcompatibleliterals(notnegationsofthesamevariable).The[formula](/page/Formula)issatisfiableifandonlyifthisgraphcontainsa[clique](/page/Clique)ofsizevertices, one for each literal occurrence in the clauses. An edge is added between two vertices if they belong to different clauses and represent compatible literals (not negations of the same variable). The [formula](/page/Formula) is satisfiable if and only if this graph contains a [clique](/page/Clique) of sizem$, as such a selects one true literal per clause without contradiction. Regarding approximability, no polynomial-time algorithm can approximate the maximum clique size to within a factor of n1−ϵn^{1-\epsilon} for any fixed ϵ>0\epsilon > 0, unless P = NP. This inapproximability result derandomizes prior work using linear-degree extractors to simulate randomness-efficient approximations, showing that the problem remains hard even for general graphs. The problem of enumerating all maximal cliques in a graph admits output-sensitive algorithms with time complexity O(3n/3⋅α(M))O(3^{n/3} \cdot \alpha(M)), where nn is the number of vertices and α(M)\alpha(M) depends on the number MM of maximal cliques output; this matches the worst-case bound on M≤3n/3M \leq 3^{n/3}, achieved by Turán graphs T(n,2)T(n,2) complemented or similar constructions. In parameterized complexity, the kk-clique problem—deciding if a graph contains a clique of size kk, parameterized by kk—is W-hard, implying it is unlikely to admit an FPT algorithm (running in f(k)⋅nO(1)f(k) \cdot n^{O(1)} time for some function ff). This hardness holds under fpt-reductions from canonical W-complete problems like multicolored clique, separating it from FPT problems while confirming its place in the W-hierarchy.

Applications

Social Networks

In social network analysis, cliques represent fully connected subgroups of individuals, such as friendship circles or mutual acquaintances, modeled as complete subgraphs in undirected graphs derived from adjacency data like surveys or interaction records. These structures capture dense interpersonal ties where every member is directly connected to all others, providing a measure of social cohesion within larger networks. A key application involves community detection, where maximal cliques identify dense subgroups that may overlap to form broader communities. The clique percolation method, introduced by Palla et al., detects such overlapping communities by linking k-cliques that share at least k-1 vertices, allowing for the identification of soft communities in like collaboration or communication graphs. This approach has been widely adopted to uncover hierarchical and interconnected social structures without assuming disjoint partitions. The , denoting the size of the largest in a network, serves as a metric for overall network cohesion, indicating the maximum of mutual connections possible. Historically, this traces back to in the 1930s, where used sociograms—early visualizations of social relations—to highlight cliques as indicators of group solidarity and interpersonal dynamics in settings like schools or organizations. Moreno's work laid foundational groundwork for viewing cliques as units of , influencing modern network studies. In collaboration networks, such as co-authorship graphs from academic publications, cliques model research teams where all members have jointly published, revealing patterns of interdisciplinary cooperation and knowledge production. For instance, analyses of physics or co-authorship data have shown that larger cliques correlate with higher , as mutual collaborations foster collective expertise. In contemporary online platforms, cliques extend to detecting echo chambers—dense subgroups where users reinforce similar viewpoints through repeated interactions, potentially amplifying polarization. Graph-based methods identify these as maximal cliques in interaction networks, such as retweet or reply graphs on , highlighting risks to information diversity.

Molecular Biology

In protein-protein interaction (PPI) networks, cliques represent densely connected subgraphs where every pair of proteins interacts, modeling stable protein complexes that perform coordinated biological functions. Maximal cliques in these networks have been used to predict functional modules, such as assemblies or signaling units, by identifying groups of proteins that are highly interconnected and thus likely to form stable complexes. For instance, an early influential approach combined clique enumeration with graph clustering and optimization to detect such modules in PPI data, revealing >50 predicted protein clusters with significant overlap to known ones. This method demonstrated that cliques capture core structures of protein complexes, aiding in the annotation of uncharacterized proteins based on guilt-by-association principles. In metabolic pathways modeled as reaction graphs, cliques identify conserved substructures, such as sets of metabolites or reactions that are fully interconnected across , indicating evolutionarily stable biochemical units. These cliques highlight dense modules where multiple reactions share substrates and products, facilitating the detection of core pathway components that are preserved despite network variations. For example, algorithms scanning for conserved cliques in metabolic networks of and eukaryotes have uncovered recurring dense patterns, such as triose cycles, that underpin essential processes like . Such analyses provide insights into pathway robustness and enable by quantifying conservation scores for clique-based motifs. Clique detection also plays a key role in analysis within molecular similarity graphs for , where nodes represent molecular fragments and edges indicate compatibility based on structural or physicochemical features. In these graphs, maximal cliques correspond to maximum common subgraphs (MCS) between query and database compounds, enabling scaffold hopping to identify novel leads with similar binding properties but diverse topologies. A notable application involves reducing molecular graphs to core scaffolds and using clique-based matching to retrieve diverse analogs, as demonstrated in against inhibitors, where it improved hit rates by focusing on shared interaction motifs. This approach integrates with quantitative structure-activity relationship (QSAR) models to prioritize candidates for synthesis and testing. The database, which curates PPI networks from multiple organisms, has been leveraged for protein clique prediction by integrating maximum clique algorithms to enhance complex identification accuracy. Researchers apply techniques like Bron-Kerbosch to STRING-derived graphs, filtering cliques by interaction confidence scores to predict novel complexes. Recent advances in single-cell (scRNA-seq) analysis employ cliques to model co-expression modules, capturing groups of genes with synchronized expression patterns indicative of regulatory programs in heterogeneous cell populations. In scRNA-seq data, genes are nodes in correlation graphs, and maximal cliques delineate tightly co-expressed modules that correspond to cell-type-specific pathways, such as circuits in tumor microenvironments. For example, the CALISTA framework uses clique detection in co-expression networks from scRNA-seq to infer lineage trajectories and functional modules, outperforming traditional clustering by better resolving rare subpopulations through dense subgraph extraction.

References

  1. https://mathworld.wolfram.com/Clique.html
  2. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture23.pdf
  3. https://mathworld.wolfram.com/CliqueNumber.html
  4. https://univ-angers.hal.science/hal-02709508v1/document
  5. https://d1b10bmlvqabco.cloudfront.net/attach/hsoyaw6eh1215z/hcf60z2lm1mde/hy4775493rba/clique.pdf
  6. https://cstheory.stackexchange.com/questions/8489/maximum-clique-practical-applications
  7. https://link.springer.com/article/10.1007/BF02289146
  8. https://www.prip.tuwien.ac.at/staffpages/yll/docs/graph_theory_book_diestel.pdf
  9. https://mathworld.wolfram.com/MaximalClique.html
  10. https://www.cs.toronto.edu/~urtasun/courses/GraphicalModels/lecture6.pdf
  11. https://www.cs.columbia.edu/~sedwards/classes/2023/4995-fall/reports/MaximalClique-report.pdf
  12. https://users.renyi.hu/~p_erdos/1988-04.pdf
  13. https://math.mit.edu/~djk/18.310/18.310F04/some_graph_theory.html
  14. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture4.pdf
  15. https://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec27-29-graphtheory.pdf
  16. https://www.cs.rpi.edu/~slotag/classes/SU19/slides/lec17.pdf
  17. https://facultyweb.kennesaw.edu/mlavrov/courses/graph-theory/lecture25.pdf
  18. https://arxiv.org/html/1102.1087v10
  19. https://mathworld.wolfram.com/TuransTheorem.html
  20. https://mathworld.wolfram.com/Erdos-StoneTheorem.html
  21. https://users.renyi.hu/~p_erdos/1961-07.pdf
  22. https://www.math.ucsd.edu/~ronspubs/90_03_erdos_ko_rado.pdf
  23. https://academic.oup.com/qjmath/article-abstract/18/1/369/1584607
  24. https://www.sciencedirect.com/science/article/pii/S0012365X18303959
  25. https://dl.acm.org/doi/10.1145/362342.362367
  26. https://www.sciencedirect.com/science/article/pii/S0166218X01002906
  27. https://ojs.aaai.org/index.php/AAAI/article/view/7536
  28. https://theory.stanford.edu/~trevisan/cs154-12/np-reductions.pdf
  29. https://link.springer.com/article/10.1007/s10107-006-0026-z
  30. https://arxiv.org/abs/2509.01261
  31. https://www.cs.cornell.edu/gomes/pdf/2025_min_arxiv_mcp.pdf
  32. https://www.cs.purdue.edu/homes/hosking/197/canon/karp.pdf
  33. https://theoryofcomputing.org/articles/v003a006/v003a006.pdf
  34. https://users.monash.edu.au/~davidwo/MoonMoser65.pdf
  35. A clique of a graph is a complete subgraph. The largest possible size is a maximum clique. A maximal clique cannot be extended by adding one more adjacent ...
  36. https://eprints.whiterose.ac.uk/id/eprint/200950/1/algorithms-13-00146-v2.pdf
  37. https://www.publichealth.columbia.edu/research/population-health-methods/social-network-analysis
  38. https://www.researchgate.net/publication/239228599_The_Development_of_Social_Network_Analysis
  39. https://www.scirp.org/journal/paperinformation?paperid=43323
  40. http://sbp-brims.org/2017/proceedings/papers/challenge_papers/MappingTheEcho-Chamber.pdf
  41. https://www.pnas.org/doi/10.1073/pnas.2032324100
  42. https://www.frontiersin.org/journals/bioengineering-and-biotechnology/articles/10.3389/fbioe.2020.00018/full
Add your contribution
Related Hubs
User Avatar
No comments yet.