Statements (36)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
graph
theoretical computer science |
| gptkbp:appearsIn |
gptkb:Karp's_21_NP-complete_problems
|
| gptkbp:approximationAlgorithm |
2-approximation algorithm exists
|
| gptkbp:category |
combinatorial optimization
theoretical computer science mathematical optimization |
| gptkbp:complexity |
NP-complete
fixed-parameter tractable (FPT) with respect to solution size |
| gptkbp:decision |
Given a graph and integer k, does there exist a vertex cover of size at most k?
|
| gptkbp:defines |
Given a graph, find the smallest set of vertices such that every edge is incident to at least one vertex in the set.
|
| gptkbp:exactSolution |
solvable in polynomial time for bipartite graphs
solvable in polynomial time for trees |
| gptkbp:field |
gptkb:mathematics
computer science |
| gptkbp:firstProvedNPCompleteBy |
gptkb:Richard_Karp
|
| gptkbp:hardnessOfApproximation |
cannot be approximated within a factor of 1.3606 unless P=NP
|
| https://www.w3.org/2000/01/rdf-schema#label |
vertex cover problem
|
| gptkbp:maximumMatchingRelation |
minimum vertex cover size is at least maximum matching size
|
| gptkbp:minimumVertexCoverIsNPHard |
true
|
| gptkbp:optimizedFor |
Find the minimum vertex cover in a graph.
|
| gptkbp:reduces |
gptkb:3-SAT
gptkb:independent_set_problem |
| gptkbp:relatedTo |
gptkb:NP-completeness
gptkb:clique_problem gptkb:independent_set_problem graph theory |
| gptkbp:usedIn |
network security
bioinformatics resource allocation scheduling social network analysis |
| gptkbp:yearNPComplete |
1972
|
| gptkbp:bfsParent |
gptkb:Polyhedral_combinatorics
gptkb:Clique_problem |
| gptkbp:bfsLayer |
6
|