ensemble minimal de couverture Algorithme: Trouver Taille optimale Couverture

Question

Le Set-couverture problème se compose des éléments suivants:

Étant donné:

1. un ensemble d'éléments U.

2. Un jeu de jeux S contenant chacun des articles de U.

Trouver l'ensemble des ensembles C telle que:

1. C est un sous-ensemble de S.
2. Les ensembles à C contient tous les articles dans U. (au moins une fois).

En option, on peut trouver le minimum C, i.e. où | C | est aussi petit que possible.

Wiki Link to Set Cover Problem

Je crois comprendre que SCP est NP-complet et PPSM (ou optimale SCP) est NP-dur, et que l'on peut utiliser l'une des nombreuses techniques pour trouver (Greedy algorithme, algorithme génétique, Réseau neuronal artificiel).

Cependant, je veux demander si trouver la taille de C (c'est-à-dire C |) est aussi NP-Hard.

Pour un exemple:

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. 

Je veux trouver | C | sans résoudre le problème. Est-ce NP-Hard? Si non, comment peut-on y arriver?

Answer 1

Si vous pouviez trouver la taille de la couverture minimale en temps P, alors vous pouvez également trouver une couverture minimale en P fois.

Pour chaque X en S, trouver la taille de la couverture minimale de U - X. Si elle est inférieure à la couverture minimale de U, alors vous savez qu'il y a une couverture minimale contenant X (note: une couverture minimale de U - X n'inclut jamais l 'ensemble X). Répétez jusqu'à ce que vous avez trouvé une couverture minimale.

Notez que la taille de la couverture est au plus | U |, et que chaque itération nécessite | S | X à considérer, donc la procédure globale est P-temps si vous avez un P-temps de trouver la taille de la couverture minimale.