Vertex Cover and Set Cover – 2

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:
B_1 = {Madras, Delhi, Pilani}.
B_2 = {Pilani, London, Paris}.
B_3 = {Delhi, Los Angeles}.
B_4 = {Madras, Paris}.

If we consider the sets B_1, B_2, B_3 , then we cover all the cities of S. Similarly, if we select B_2, B_3, B_4 , 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 = {a_1, a_2, ..., a_n } of n elements.

We are also given certain subsets of the set S:B_1, B_2, ..., B_m .

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.)

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: