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.
All labels observed (1)
| Label | Occurrences |
|---|---|
| Clique problem canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T7666073 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Clique problem Context triple: [NP-completeness, hasCanonicalProblem, Clique problem]
-
A.
P versus NP problem
The P versus NP problem is a central unsolved question in theoretical computer science that asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.
-
B.
Max-3-SAT
Max-3-SAT is an optimization variant of the Boolean satisfiability problem where the goal is to maximize the number of satisfied clauses, each containing exactly three literals, and it serves as a central problem in the study of approximation algorithms and hardness of approximation.
-
C.
NP-completeness
NP-completeness is a central concept in computational complexity theory that classifies decision problems believed to be among the hardest in NP, such that a polynomial-time solution to any one of them would yield polynomial-time solutions to all problems in NP.
-
D.
Steiner tree problem
The Steiner tree problem is a classic optimization problem in combinatorial mathematics and computer science that seeks the shortest network of line segments connecting a given set of points, potentially adding extra intermediate points to minimize total length.
-
E.
A Combinatorial Problem
"A Combinatorial Problem" is a classic mathematical paper by N. G. de Bruijn that introduces and analyzes a fundamental counting problem in combinatorics.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Clique problem Target entity description: 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.
-
A.
P versus NP problem
The P versus NP problem is a central unsolved question in theoretical computer science that asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.
-
B.
Max-3-SAT
Max-3-SAT is an optimization variant of the Boolean satisfiability problem where the goal is to maximize the number of satisfied clauses, each containing exactly three literals, and it serves as a central problem in the study of approximation algorithms and hardness of approximation.
-
C.
NP-completeness
NP-completeness is a central concept in computational complexity theory that classifies decision problems believed to be among the hardest in NP, such that a polynomial-time solution to any one of them would yield polynomial-time solutions to all problems in NP.
-
D.
Steiner tree problem
The Steiner tree problem is a classic optimization problem in combinatorial mathematics and computer science that seeks the shortest network of line segments connecting a given set of points, potentially adding extra intermediate points to minimize total length.
-
E.
A Combinatorial Problem
"A Combinatorial Problem" is a classic mathematical paper by N. G. de Bruijn that introduces and analyzes a fundamental counting problem in combinatorics.
- F. None of above. chosen
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
ⓘ
linked to:
Richard Karp
|
| isComplementaryTo | independent set problem ⓘ |
| isHardFor | NP ⓘ |
| knownSince | 1970s ⓘ |
| listedIn | Karp's 21 NP-complete problems ⓘ |
| 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 ⓘ |
| publicationYear | 1972 ⓘ |
| reductionFrom | 3-SAT ⓘ |
| reductionFrom | Boolean satisfiability problem ⓘ |
| 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 ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Clique problem Description of subject: 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.
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.