# Vertex Cover and Set Cover – 2

November 13, 2009 Leave a comment

Having looked briefly at the **Vertex Cover problem**, here we shall define the** Set Cover problem.**

As the name suggests, we have a set, and we need to “cover” something.

Consider the following example:

We have a set of cities, S = {Madras, Delhi, Pilani, Los Angeles, London, Paris}.

We are also given the following subsets of S:

= {Madras, Delhi, Pilani}.

= {Pilani, London, Paris}.

= {Delhi, Los Angeles}.

= {Madras, Paris}.

If we consider the sets , then we cover all the cities of S. Similarly, if we select , we again cover all cities of S. (A city is “covered” if it is part of any of the subsets that we select.)

We can now state the Set Cover Problem more formally.

**We are given a set, S = {} of elements.**

**We are also given certain subsets of the set S:.**

**We wish to find a collection of these subsets so as to cover the set S.** We wish to find a collection of minimum number of subsets that covers the set S. (The number of subsets in the chosen collection is called the size of the Set Cover.)

The Set Cover Problem is defined as a vatriant of the above problem. Instead of finding a minimum-sized collection of subsets, we are given a positive integer, k, and are asked the following question: **“Does there exist a Set Cover of size less than or equal to k?”.**

(Note the similarity with the definition of the Vertex Cover problem.)