Vertex cover problem

computer science, the Vertex Cover Problem is an NP-complete problem in complexity theory.

A vertex cover of an undirected graph <math>G = (V, E)<math> is a subset <math>V'<math> of the vertices of the graph which contains at least one of the two endpoints of each edge:

<math>V' \subseteq V: \forall \{a, b\} \in E : a \in V' \or b \in V'<math>.

In the graph at the 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 can also be stated as a decision problem:

INSTANCE: A graph <math>G<math> and a positive integer <math>k<math>.

QUESTION: Is there a vertex cover of size <math>k<math> or less for <math>G<math>?

Vertex cover is NP-complete, which means it is unlikely that there is an efficient algorithm to solve it. NP-completeness can be proven by reduction from 3-satisfiability.

One can find a factor-2 approximation by repeatedly taking both endpoints of an edge into the vertex cover, removing them from the graph. No better constant-factor approximation is known; the problem is APX-complete, i.e., it cannot be approximated arbitrarily well.

A brute force algorithm to find a vertex cover in a graph is to list all subsets of vertices of size <math>k<math> and check each one to see whether it forms a vertex cover. This algorithm is exponential in <math>k<math>, but not in the size of the graph, i.e., vertex cover is fixed-parameter tractable with respect to <math>k<math>.

[Top]


View Live Article	This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License

Vertex cover problem

See Also