Vertex cover problem

GPTKB entity

Statements (27)
Predicate Object
gptkbp:instanceOf graph
theoretical computer science
gptkbp:application network security
bioinformatics
resource allocation
gptkbp:approximationAlgorithm 2-approximation exists
gptkbp:citation Richard M. Karp, 1972
gptkbp:complementaryProblem maximum independent set problem
gptkbp:complexity NP-complete
fixed-parameter tractable for parameter k
gptkbp:decision Does a vertex cover of size k exist?
gptkbp:field gptkb:mathematics
computer science
gptkbp:firstDescribed gptkb:Karp's_21_NP-complete_problems
gptkbp:hardness APX-hard
https://www.w3.org/2000/01/rdf-schema#label Vertex cover problem
gptkbp:input graph
gptkbp:optimizedFor Find the smallest vertex cover
gptkbp:output vertex cover of minimum size
gptkbp:relatedTo gptkb:independent_set_problem
vertex cover
NP-complete problem
set cover problem
matching in graphs
gptkbp:solvableInPolynomialTime for bipartite graphs
gptkbp:bfsParent gptkb:NP-completeness
gptkbp:bfsLayer 5