next up previous contents index CD CD Algorithms
Next: Traveling Salesman Problem Up: Graph Problems: Hard Problems Previous: Independent Set

Vertex Cover



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

Problem description: What is the smallest subset of tex2html_wrap_inline29343 such that each tex2html_wrap_inline29345 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 tex2html_wrap_inline29347 of the universal set tex2html_wrap_inline29349 .   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 gif 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 tex2html_wrap_inline29351 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 tex2html_wrap_inline29353 times worse than the optimal cover.

Much better is the following approximation algorithm, discussed in Section gif, 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 gif) 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 gif for details.

Combinatorica [Ski90] provides (slow) Mathematica implementations of cliques, independent sets, and vertex covers.     See Section gif 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 tex2html_wrap_inline29355 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 tex2html_wrap_inline29357 times optimal is due to [Joh74] and is presented in [PS82].

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

next up previous contents index CD CD Algorithms
Next: Traveling Salesman Problem Up: Graph Problems: Hard Problems Previous: Independent Set

Mon Jun 2 23:33:50 EDT 1997