Clique (graph theory)
In graph theory, a clique describes a subset of nodes in an undirected graph in which each pair of nodes is connected by an edge. To decide whether a graph contains a clique of a certain minimum size is called a clique problem and, like finding the largest cliques, is algorithmically difficult ( NP-complete ).
Let be an undirected graph without multiple edges and a subset of . A clique is a subset of that induces a complete subgraph . If there is a clique, then for the subgraph , where all edges out contain that connect two nodes in , that any two different nodes and out are connected to each other by an edge.
A clique of is called a maximum if you cannot add another node from to , so that together with is a clique. If there is no clique in any clique that contains more elements than it is called the largest clique . The number of elements in a largest clique is called the clique number .
Problems and complexities
The decision problem for a graph and a natural number to decide whether a clique contains at least the size is called the clique problem (CLIQUE) . The associated optimization problem asks for the number of cliques in a graph. The associated search problem asks for a largest clique. These three problems are polynomially equivalent.
The clique problem is one of Karp's 21 NP-complete problems . The associated optimization and search problems are NP-equivalent . To prove the NP severity of the clique problem, there is a reduction from 3-SAT to the clique problem.
A largest clique, however, can be calculated in polynomial time if the complement graph is bipartite . In fact, it is even more true that the number of cliques in perfect graphs can be calculated in polynomial time. Since the chromatic number and the clique number are identical in such graphs, their chromatic number can also be calculated in polynomial time. A simple greedy algorithm can be used to calculate a maximum clique .
- Algorithms - Clique. In: NetworkX 2.2 documentation. Retrieved October 25, 2018 .