Vertex cover problem

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

Referenced By