Main Page | See live article | Alphabetical index 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 TODO See Also Graph theory This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.