Vertex Cover and Set Cover – 1

Here we will look at two very interesting problems. One is known as the Vertex Cover Problem, and the other as the Set Cover Problem. Both are quite simple to define, and visualize (and equally difficult to solve efficiently🙂 ).

Let us consider the Vertex Cover Problem first. As the name suggests, we have to “cover” something. We are given an undirected graph, G = (V, E). We need to select a set of vertices from V, so that all edges are “covered” by this set of vertices.

What exactly do we mean by covering? A vertex “covers” all edges that are incident upon it. This does seem to be quite a natural definition.

Example:

vertex_cover1

In the above graph, the vertex, v2 covers edges {v2,v1}, {v2,v3}, {v2,v4}. Analogously, edge {v2,v4} is covered by vertices, v2 and v4. (It is clear that every edge can be covered by at most two vertices. No vertex other than its end points can cover an edge.)

A set of vertices, S, covers all edges that are incident upon any vertex of S.

For example, in the above graph, the vertex set {v3, v4, v5} covers edges {v3,v2}, {v4,v2} and {v4,v5}.

Now that we know what it means to cover an edge, we repeat what we stated earlier the question: What is a Vertex Cover? A Vertex Cover is simply a set of vertices which covers all edges of the graph.

For instance, in the above graph, the set {v1, v3, v4} is a vertex cover. (Note that the set, V is trivially a vertex cover for the graph, G = (V, E). )

From the above, it might seem that finding a vertex cover seems to be a simple task, and as such does not merit special mention. Indeed that is true.

But what is not so easy is finding a Vertex Cover of minimum possible cardinality, i.e. we need to cover all edges of the graph using as few vertices as possible.

Specifically, we are given an undirected graph G = (V, E) and a positive integer, k, and are asked to find out whether there exists a Vertex Cover of size (i.e. cardinality) less than or equal to k. This now, is the definition for our Vertex Cover Problem (and as stated at the very beginning, this is not the easiest problem to solve🙂 ).

Let us go back to the graph drawn above, and ask the following questions:

(1) Does there exist a Vertex Cover of size \leq 3 ?
The answer is an emphatic, “Yes”. (The set {v1, v3, v4} is a proof that our answer is correct.)

(2) Does there exist a Vertex Cover of size \leq 2 ?
Again, the answer is “yes”. (The set, {v2, v4} is a proof of the correctness of the answer.)

(3) Does there exist a Vertex Cover of size \leq 1 ?
Here, the answer is “No”. And how do we verify this answer? One way is the obvious brute force method. Enumerate all sets of vertices of size \leq 1 , and check whether any of them is a vertex cover. If none of them is, then the answer is correct.

(Note: It is highly possible that there would be errors in this series of posts. I am sorry for that. It would be great if you could point them out.)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: