Vertex Cover and Set Cover – 4

Question: We are given an instance of the Vertex Cover problem. We are also given an algorithm for the Set Cover problem. Using this algorithm as a black box, solve the given instance of the Vertex Cover problem.

Solution:

Given instance of Vertex Cover problem: undirected graph, G = (V, E); positive integer k.
Question: Does G have a vertex cover of size at most k?

===

[To recapitulate, this is what an instance of the Set Cover problem looks like:

Given: Set S = { a_1, a_2, ..., a_p }; subsets of S: B_1, B_2, ..., B_q ; positive integer k.
Question: Does S have a Set Cover of size at most k? ]

===

We have the following Vertex Cover instance specified to us in the question:

E = { e_1, e_2, ...., e_m }.

V = { v_1, v_2, ..., v_n }.

We will convert this into an instance of the Set Cover problem, and apply the algorithm for the Set Cover problem to solve it.

Idea:

1. In the Vertex Cover problem, we need to cover edges of the graph. In the Set Cover problem we need to cover elements of a set, S. So, we will convert each edge into an element of a set, S, and try to cover that set.

2. In the Vertex Cover problem, we need to cover the edges using limited number of vertices. In the Set Cover problem, we need to cover elements of a set using limited number of subsets. So this gives us the idea of mapping a vertex of the Vertex Cover problem instance to a subset of the Set Cover problem instance.

Now, what all elements does a subset B_i cover? It covers all the elements contained in B_i .

Now again, what all edges does a vertex, v_i cover? It covers all edges that are incident upon it.

So, now the conversion of the Vertex Cover instance into a Set Cover instance is much clearer.

1. Corresponding to each edge, e_i , introduce an element a_i . (Call this set of m elements, corresponding to the m edges, as S.)

2. Corresponding to each vertex, v_i , introduce a subset of S, called B_i .

The set B_i contains all elements a_j for which the corresponding edge, e_j is incident upon vertex, v_i .

(For example, if edges e_3, e_5, e_7 are incident upon vertex, v_2 , then set, B_2 = { a_3, a_5, a_7 }. )

We were asked to find whether a Vertex Cover of size at most k exists. In the Set Cover instance that we have produced, this gets converted into the question: Does there exist a Set Cover of size at most k?

We have thus completely specified an instance of the Set Cover problem, derived from the original Vertex Cover problem that we were presented with.

Now, we can apply the algorithm to the Set Cover problem to solve this new instance. (The instance of the Set Cover problem that we derive from the Vertex Cover instance, is known as a reduced instance. i.e. The Vertex Cover problem was reduced to the Set Cover problem.)

Question: Does this reduced instance of the Set Cover problem have a set cover of size at most k?

If the answer is “yes”: This implies that there exists a collection of at most k subsets B_i through which we covered all elements, a_j . If we go back to the original Vertex Cover instance, this implies that there exists a subset of at most k vertices v_i which covers all edges, e_i of the graph. Hence, the answer to the Vertex Cover instance is also “yes”.

In other words: If the answer to the reduced Set Cover instance is “yes”, then the answer to the original Vertex Cover instance is “yes”.

If the answer of the reduced Set Cover instance is “no”: This implies that we cannot cover all elements of S using any collection of  at most k subsets.

This implies that we cannot cover all edges of the graph, G using any set of at most k vertices. (We can prove this by contradiction: If suppose, we are able to cover all edges using a set of at most k vertices, then by using the corresponding collection of at most k subsets, we can cover all elements of S. i.e. We arrive at a contradiction, and hence, we cannot cover all edges of the graph G using any set of at most k vertices.) This means that the answer to the Vertex Cover instance is “no”.

In other words: If the answer to the reduced Set Cover instance is “no”, then the answer to the original Vertex Cover instance is “no”.

====

Thus, in order to solve the original Vertex Cover instance:

1. We reduced it to an instance of the Set Cover problem.

2. We solved that instance using an algorithm for the Set Cover problem.

3. If the answer to the Set Cover instance comes out to be “yes”, it implies that answer to original Vertex Cover instance is “yes”.

4. Else (if the answer to the Set Cover instance is “no”), the answer to the orginal Vertex Cover instance is “no”.

====

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: