**Input description**: A graph *G*=(*V*,*E*).

**Problem description**: What is the smallest subset of such that
each contains at least one vertex of *S*?

**Discussion**: Vertex cover is a special case of the more general *set cover*
problem, which takes as input an arbitrary collection of
subsets of the universal set .
We seek the smallest subset of subsets from *S* whose union is *U*.
Set cover arises in many applications, including Boolean logic minimization.
See Section for a discussion of set cover.

To turn vertex cover into a set cover problem, let *U* be the complete
set of edges, and create to be the set of edges incident on vertex *i*.
A set of vertices defines a vertex cover in graph *G* iff the corresponding
subsets define a set cover in the given instance.
However, since each edge can be in only two different subsets,
vertex cover instances are
simpler than general set cover.
The primary reason for distinguishing between the two problems is that
vertex cover is a relative lightweight among NP-complete
problems, and so can be effectively solved.

Vertex cover and independent set are very closely related graph
problems.
Since every edge in *E* is (by definition) incident on a vertex in a cover *S*,
there can be no edge for which both endpoints are not in *S*.
Thus *V-S* must be an independent set.
Further, since minimizing *S* is the same as maximizing *V-S*,
a minimum vertex cover defines a maximum independent set, and vice versa.
This equivalence means that if you have a program that solves
independent set, you can use it on your vertex cover problem.
Having two ways of looking at it can be helpful
if you expect that either the cover or independent set is likely
to contain only a few vertices, for it might pay to search all
possible pairs or triples of vertices if you think that it
will pay off.

The simplest heuristic for vertex cover selects the vertex with highest degree, adds it to the cover, deletes all adjacent edges, and then repeats until the graph is empty. With the right data structures, this can be done in linear time, and the cover you get ``usually'' should be ``pretty good''. However, for certain input graphs the resulting cover can be times worse than the optimal cover.

Much better is the following approximation algorithm,
discussed in Section ,
which always finds a vertex cover
whose size is at most twice as large as optimal.
Find a *maximal* matching in the graph, i.e. a set of edges
no two of which share a vertex in common and that cannot be made larger
by adding additional edges.
Such a maximal matching can be built incrementally,
by picking an arbitrary edge *e*
in the graph, deleting any edge sharing a vertex with *e*, and repeating
until the graph is out of edges.
Taking *both* of the vertices for each edge in the
matching gives us a vertex cover, since we only delete edges incident to
one of these vertices and eventually delete all the edges.
Because *any* vertex cover must contain *at least*
one of the two vertices in each matching edge just to cover the matching,
this cover must be at most twice as large as that of the minimum cover.

This heuristic can be tweaked to make it perform somewhat better in practice, without losing the performance guarantee or costing too much extra time. We can select the matching edges so as to ``kill off'' as many edges as possible, which should reduce the size of the maximal matching and hence the number of pairs of vertices in the vertex cover. Also, some vertices selected for our cover may in fact not be necessary, since all of their incident edges could also have been covered using other selected vertices. By making a second pass through our cover, we can identify and delete these losers. If we are really lucky, we might halve the size of our cover using these techniques.

A problem that might seem closely related to vertex cover is *edge cover*,
which seeks the smallest set of edges such that each vertex is included
in one of the edges.
In fact, edge cover can be efficiently solved by finding a maximum
cardinality matching in *G* (see Section ) and
then selecting arbitrary edges
to account for the unmatched vertices.

**Implementations**: Programs for the closely related problems of finding
cliques and independent sets were sought for the
Second DIMACS Implementation Challenge, held in October 1993.
See Section for details.

Combinatorica [Ski90] provides (slow) Mathematica implementations of cliques, independent sets, and vertex covers. See Section for further information on Combinatorica.

Neural-network heuristics for vertex cover and related problems such as clique and vertex coloring have been implemented in C and Mathematica by Laura Sanchis and Arun Jagota, and are available in the algorithm repository http://www.cs.sunysb.edu/ algorith.

**Notes**: Good expositions of the proof that vertex-cover is NP-complete [Kar72]
include [CLR90, GJ79, Man89].
Good expositions on the 2-approximation algorithm include [CLR90].
The example that the greedy algorithm can be as bad as times
optimal is due to [Joh74] and is presented in [PS82].

**Related Problems**: Independent set (see page ),
set cover (see page ).

Mon Jun 2 23:33:50 EDT 1997