Clique problem
E679893
The Clique problem is a classic NP-complete decision problem in graph theory that asks whether a graph contains a fully connected subgraph (clique) of at least a given size.
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
computational problem
ⓘ
decision problem ⓘ |
| applicationArea |
bioinformatics
ⓘ
computational chemistry ⓘ pattern recognition ⓘ social network analysis ⓘ |
| approximation | hard to approximate within any reasonable factor (under standard assumptions) ⓘ |
| asksFor | existence of a clique of at least a given size ⓘ |
| complexityClass | NP-complete ⓘ |
| field |
graph theory
ⓘ
theoretical computer science ⓘ |
| graphType | undirected graph ⓘ |
| hasCertificate | set of vertices forming a clique of size at least k ⓘ |
| inClass | NP ⓘ |
| input |
integer k
ⓘ
simple graph ⓘ |
| introducedBy | Richard M. Karp NERFINISHED ⓘ |
| isComplementaryTo | independent set problem ⓘ |
| isHardFor | NP NERFINISHED ⓘ |
| knownSince | 1970s ⓘ |
| listedIn | Karp's 21 NP-complete problems NERFINISHED ⓘ |
| optimizationVariant | maximum clique problem ⓘ |
| output |
NO if the graph does not contain a clique of size at least k
ⓘ
YES if the graph contains a clique of size at least k ⓘ |
| parameterizedComplexity | W[1]-complete ⓘ |
| parameterizedVariant | parameterized by clique size k ⓘ |
| publication | Reducibility Among Combinatorial Problems NERFINISHED ⓘ |
| publicationYear | 1972 ⓘ |
| reductionFrom | 3-SAT ⓘ |
| reductionFrom | Boolean satisfiability problem NERFINISHED ⓘ |
| reductionTo |
independent set problem
ⓘ
vertex cover problem ⓘ |
| relatedConcept |
NP-completeness
ⓘ
clique ⓘ complete subgraph ⓘ independent set problem ⓘ maximum clique problem ⓘ vertex cover problem ⓘ |
| requires | checking pairwise adjacency among vertices in candidate clique ⓘ |
| searchVariant | find a clique of size at least k ⓘ |
| statusIfPEqualsNP | would be solvable in polynomial time ⓘ |
| typicalDecisionQuestion | Does the graph contain a clique of size at least k? ⓘ |
| typicalRepresentation |
adjacency list
ⓘ
adjacency matrix ⓘ |
| usedIn |
algorithm design benchmarks
ⓘ
complexity theory reductions ⓘ |
| verificationTime | polynomial time ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.