# Vertex Cover and Set Cover – 4

November 13, 2009 Leave a comment

**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 = { }; subsets of S: ; 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 = { }.

V = { }.

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 cover? It covers all the elements contained in .

Now again, what all edges does a vertex, 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, , introduce an element . (Call this set of m elements, corresponding to the m edges, as S.)**

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

**The set contains all elements for which the corresponding edge, is incident upon vertex, .**

(For example, if edges are incident upon vertex, , then set, { }. )

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 through which we covered all elements, . If we go back to the original Vertex Cover instance, this implies that there exists a subset of at most k vertices which covers all edges, 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”.*

====