Problème de couverture par ensembles

En informatique théorique, le problème de couverture par ensembles (Set Cover problem en anglais) est un problème d'algorithmique particulièrement important car c'est l'un des 21 problèmes NP-complets de Karp . Étant donné un ensemble A, on dit qu'un élément e est couvert par A si e appartient à A. Étant donné un ensemble U et une famille S de sous-ensembles de U, le problème consiste à couvrir tous les éléments U avec une sous-famille de S la plus petite possible. Une version plus générale consiste à assigner des poids aux éléments de S, et à chercher la sous-famille de poids minimal. On considère un ensemble de cinq éléments à couvrir : . On considère les sous-ensembles : et . On essaye de couvrir tous les éléments avec des sous-ensembles. Par exemple est une couverture, puisque chaque élément est dans au moins un des sous-ensembles. La couverture qui utilise le moins de sous-ensembles est , c'est donc cette couverture que l'on cherche à calculer. Le problème de décision est le suivant : Entrée : un entier , un ensemble fini et un sous-ensemble de l'ensemble des parties de Question : existe-il un sous-ensemble de , de taille inférieure à , tel que l'union des éléments présents dans les sous-ensembles de est égal à ? Le problème d'optimisation associé consiste à minimiser le nombre de sous-ensembles utilisés. Dans une forme plus générale du problème, à chaque ensemble on associe un poids , et le but est de minimiser la somme des poids de la couverture. Le problème de couverture par ensembles est NP-difficile (et NP-complet dans sa forme décisionnelle). Une des preuves classiques est une réduction du problème de couverture par sommets. Il est fructueux d'exprimer ce problème comme un problème d'optimisation linéaire en nombres entiers. En prenant une variable pour chaque sous-ensemble, le programme linéaire naturel est le suivant : Si l'on associe un poids à chaque ensemble, le problème devient : Le problème de couverture de sommets est un cas particulier de ce problème, sur un graphe.