Vertex Cover Problem

A '' Vertex Cover '' of an undirected Graph

G = (V, E)

is a subset

V'

of the vertices of the graph which contains at least one of the two endpoints of each edge:
:

V' \subseteq V: orall \{a, b\} \in E : a \in V' \or b \in V'

.
In the graph at the right, {1,3,5,6} is an example of a vertex cover. {2,4,5} is another, smaller 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

G

and a positive integer

k

.
:QUESTION: Is there a vertex cover of size

k

or less for

G

?

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 or, as Karp did, by reduction from the Clique Problem . Vertex cover remains NP-complete even in Cubic Graph s and even in Planar Graph s of degree at most 3.¹

Vertex cover is closely related to Independent Set Problem :

V'

is a vertex cover iff its complement,

V \setminus V'

, is an independent set. It follows that a graph with

n

vertices has a vertex cover of size

k

if and only if the graph has an independent set of size

n-k

.

One can find a factor-2 Approximation by repeatedly taking ''both'' endpoints of an edge into the vertex cover, then 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.
More precisely, minimum vertex cover is known to be approximable within

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

	CATEGORIES ABOUT VERTEX COVER PROBLEM

	graph theory

	np-complete problems

Information About

Vertex Cover Problem