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 ).
