CODEWITHSUNDEEP
algorithmoptimizationnpset-theoryset-cover
JD009
JD009

Reputation: 49

Minimum Set Cover Algorithm: Finding Size of Optimal Cover

The Set-Cover Problem consists of the following:

Given:

  1. A set of Items U.

  2. A set of Sets S each of which contain items from U.

Find the set of sets C such that:

  1. C is a subset of S.
  2. The sets in C contains all items in U. (at least once).

Optionally, one can find the Minimum C, i.e where |C| is as small as possible.

Wiki Link to Set Cover Problem

I understand that SCP is NP-Complete and MSCP (or Optimal SCP) is NP-Hard, and that one may use one of many techniques to find it (Greedy Algorithm, Genetic Algorithm, Artificial Neural Network).

However, I want to ask whether finding the size of C (i.e |C|) is NP-Hard too.

To show an example:

Given the following S:
[2 4 6], [1 3 5], [3 2 1], [5 4 6], [2 3 5]

And U being: 
1 2 3 4 5 6

A possible Set-Cover (C) is:
[2 4 6], [1 3 5], [2 3 5]

However, the Optimal Set-Cover (C) is:
[3 2 1], [5 4 6]

Thus |C|, the size of the Optimal Set-Cover is 2.

I want to find |C| without solving the problem. Is this NP-Hard? If not, How can one go about finding this?

Upvotes: 0

Views: 981

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58221

If you could find the size of the minimum cover in P time, then so too could you find a minimum cover in P time.

For each X in S, find the size of the minimum cover of U - X. If it's one less than the size of the minimum cover of U then you know there's a minimum cover containing X (note: a minimum cover of U - X never includes the set X). Repeat until you've found a minimum cover.

Note that the size of the cover is at most |U|, and each iteration requires |S| X's to consider, so the overall procedure is P-time if you've got a P-time way of finding the size of the minimum cover.

Upvotes: 3

Related Questions