+- MKLab (https://mklab.gr)
+-- Forum: [INDEX] (https://mklab.gr/forumdisplay.php?fid=1)
+--- Forum: MATHEMATICS (https://mklab.gr/forumdisplay.php?fid=3)
+---- Forum: ARTICLES (https://mklab.gr/forumdisplay.php?fid=13)
+----- Forum: GRAPHS AND NETWORKS (https://mklab.gr/forumdisplay.php?fid=202)
+----- Thread: Clique problem (/showthread.php?tid=1901)
Clique problem - mklabgr - 09-07-2026
Summary
The clique problem is a fundamental problem in graph theory and theoretical computer science. Given an undirected graph $G=(V,E)$, a clique is a subset of vertices in which every pair of vertices is connected by an edge—in other words, the vertices form a complete subgraph. Several related computational problems arise: finding a maximum clique (the clique containing the largest possible number of vertices), finding all maximal cliques (cliques that cannot be enlarged), or deciding whether a graph contains a clique of size at least $k$. The size of a maximum clique is called the clique number, usually denoted $\omega(G)$. A useful duality is that a clique in $G$ corresponds exactly to an independent set in the complement graph $\overline{G}$.
Computationally, the problem is famous for its difficulty. The decision version—determining whether $G$ contains a $k$-clique—is NP-complete, while finding a maximum clique is NP-hard and is also exceptionally difficult to approximate efficiently. A straightforward brute-force method checks the $\binom{n}{k}$ possible sets of $k$ vertices, requiring roughly $O(n^k k^2)$ time when $k$ is variable. By contrast, finding just one maximal clique can be done greedily in linear time. For enumerating all maximal cliques, the classical Bron–Kerbosch algorithm is widely used; optimized versions achieve worst-case time $O(3^{n/3})$, which is essentially optimal because an $n$-vertex graph can itself contain as many as $3^{n/3}$ maximal cliques.
The clique problem has important applications beyond pure graph theory. In a social network, for example, vertices can represent people and edges mutual acquaintances, so a clique represents a group in which everyone knows everyone else. Similar clique-search techniques appear in bioinformatics, protein-interaction analysis, computational chemistry, molecular matching, evolutionary-tree reconstruction, automatic test generation, and even mathematical research. Much of modern research therefore focuses either on faster algorithms for special graph classes or on proving precisely why the general clique problem cannot be solved efficiently under standard complexity assumptions such as $P\ne NP$.
Key takeaways
- Area: Graph Theory, Combinatorics, Algorithms, Computational Complexity.
- Clique: a complete subgraph; every pair of its vertices is adjacent.
- Maximum clique: largest clique; its size is $\omega(G)$.
- Complexity: the $k$-clique decision problem is NP-complete, making the clique problem one of the classical examples of computational intractability.
ARTICLE