|
gptkbp:instanceOf
|
theoretical computer science
|
|
gptkbp:approximation
|
hard to approximate
|
|
gptkbp:citation
|
gptkb:Garey_and_Johnson,_Computers_and_Intractability,_1979
|
|
gptkbp:complementProblem
|
gptkb:independent_set_problem
|
|
gptkbp:complexity
|
NP-complete
W[1]-complete
|
|
gptkbp:decision
|
yes
|
|
gptkbp:defines
|
Given a graph G and integer k, does G contain a clique of size k?
|
|
gptkbp:famousAlgorithm
|
gptkb:Robson's_algorithm
gptkb:Bron–Kerbosch_algorithm
|
|
gptkbp:field
|
computer science
graph theory
|
|
gptkbp:firstDescribed
|
1970s
|
|
https://www.w3.org/2000/01/rdf-schema#label
|
clique problem
|
|
gptkbp:input
|
graph
integer k
|
|
gptkbp:optimizedFor
|
gptkb:maximum_clique_problem
|
|
gptkbp:output
|
yes/no
|
|
gptkbp:reduces
|
gptkb:3-SAT
gptkb:vertex_cover_problem
|
|
gptkbp:relatedTo
|
gptkb:clique_(graph_theory)
gptkb:independent_set_problem
gptkb:vertex_cover_problem
|
|
gptkbp:solvableInPolynomialTime
|
no (unless P=NP)
|
|
gptkbp:usedIn
|
coding theory
computational chemistry
bioinformatics
social network analysis
|
|
gptkbp:bfsParent
|
gptkb:Polyhedral_combinatorics
|
|
gptkbp:bfsLayer
|
6
|