Vertex cover problem
In
computer science, the
Vertex Cover Problem is an
NP-complete problem in
complexity theory.
A vertex cover in a graph is a subset of the verticies of the graph, chosen with the property that one of the endpoints of each edge is in the subset. In the graph at right, {1,3,5,6} is an example of a vertex cover.
The vertex cover problem is the optimization problem of finding a vertex cover of minimum size in a graph. The problem is a decision problem, so we wonder if a vertex cover of size k exists in the graph.
- VERTEX COVER = {<G, k>| k <= the number of vertices in G, G is a graph with a clique of size k or less}
A
brute force algorithm to find a vertex cover in a graph is to list all subsets of vertices,
V and check each one to see if it forms a vertex cover. The algorithm is polynomial if
k is constant, but not if
k is, say, |
V|/2.
Proof
See Also
