Clique problem

The clique problem asks for a largest complete subgraph of a given graph, or whether the graph contains a clique of at least a specified size. Its decision version is NP-complete.

Clique: A set of vertices in a graph in which every pair is joined by an edge. The problem searches for the largest such vertex set.
Independent set: A set of vertices in a graph with no edges between any pair. A clique in a graph is an independent set in its complement.
Social network analysis: The analysis of relationships and structures represented by social networks. Cliques identify groups in which every member is connected to every other member.
NP-completeness: The classification of decision problems that are in NP and as hard as every problem in NP. The decision version of clique is a canonical NP-complete problem.
Maximum clique: A clique with the greatest number of vertices in a given graph. Finding this object is the optimization form of the problem.
Vertex cover: A set of vertices that touches every edge in a graph. Complementation links clique size to vertex-cover size.
Association graph: A graph whose vertices represent candidate correspondences and whose edges encode pairwise compatibility. Large cliques encode mutually consistent correspondences in graph-matching problems.
Karp's 21 NP-complete problems: A landmark 1972 list of 21 problems shown NP-complete by Richard Karp. Clique appears among the problems that established NP-completeness as a practical classification.
Parameterized complexity: The study of algorithmic difficulty when measured against a chosen parameter of the input. Clique is a central example of a problem whose parameterized complexity depends sharply on clique size.
Biclique problem: The problem of finding a largest complete bipartite subgraph in a graph. Unlike clique, biclique requires edges across two vertex sets, not among every pair in one set.

Linked from 1 page