Problème de la couverture exacte - Définition

Introduction

Le problème de la couverture exacte est un problème d'optimisation combinatoire NP-complet qui fait partie des 21 problèmes NP-complets de Karp.

Énoncé

Étant donné un univers U d'éléments et une collection d'ensembles, une couverture exacte est une collection de sous-ensembles de telle que tout élément dans U est aussi un élément dans exactement un des ensembles de .

En d'autres termes, une couverture exacte est une sous-collection de qui est une partition de U : les ensembles dans sont disjoints et leur union est U.

Étant donné un univers U d'éléments et une collection d'ensembles, le problème de la couverture exacte consiste en trouver une couverture exacte ou bien de déterminer qu'il n'en existe pas.

Le problème de la couverture exacte est un exemple d'un problème de satisfaction de contraintes.

Exemple 1

Soit U = {0, 1, 2, 3, 4, ...} l'univers des entiers naturels et soit = {E, I, P} une collection de trois ensembles d'entiers naturels :

• les nombres pairs E = {0, 2, 4, 6, 8, ...};
• les nombres impairs I = {1, 3, 5, 7, 9, ...}; et
• les nombres premiers P = {2, 3, 5, 7, ...}.

Alors, la sous-collection = {E, I} est une couverture exacte, puisque chaque nombre naturel est soit pair ou impair, mais pas les deux.

Par contre, {E, P} n'est pas une couverture exacte, puisque certains nombres naturels ne sont contenus dans aucun ensemble : par exemple, 1 est ni pair ni premier. De plus, certains nombres naturels sont contenus dans plusieurs ensembles : par exemple, 2 est et pair et premier.

Exemple 2

Soit U = {1, 2, 3, 4, 5, 6, 7} un univers de 7 éléments et soit = {A, B, C, D, E, F} une collection de 6 ensembles :

• A = {1, 4, 7};
• B = {1, 4};
• C = {4, 5, 7};
• D = {3, 5, 6};
• E = {2, 3, 6, 7}; et
• F = {2, 7}.

Alors, la sous-collection = {B, D, F} est une couverture exacte, puisque chaque élément est contenu dans exactement un des ensembles B = {1, 4}, D = {3, 5, 6}, ou F = {2, 7}.

De plus, {B, D, F} est la seule couverture exacte, comme le démontre l'argument suivant : Une couverture exacte doit couvrir 1 et A et B sont les seuls ensemble contenant 1, ainsi une couverture exacte doit contenir A ou B, mais non les deux. Si une couverture exacte contient A, alors elle ne contient ni B, C, E, ou F, comme chacun de ces ensemble ont au moins un élément en commun avec A. Alors D est le seul ensemble restant qui soit une partie de la couverture exacte, mais la collection {A, D} ne couvre pas l'élément 2. En conclusion, il n'existe pas de couverture exacte contenant A. D'un autre côté, si une couverture exacte contient B, alors elle n'inclut ni A ni C, comme chacun de ces ensembles ont au moins un élément en commun avec B. Alors D est le seul ensemble restant qui contient 5, donc D doit être une partie de la couverture exacte. Si une couverture exacte contient D, alors elle ne contient pas E, comme D et E ont les éléments 3 et 6 en commun. Alors F est le seul ensemble restant qui soit une partie de la couverture exacte, et la collection {B, D, F} est vraiment une couverture exacte. Voir l'algorithme X de Knuth pour une version de cet argument basée sur une matrice.

Généralisations

Bien que le problème standard de la couverture exacte implique une collection d'ensembles contenant des éléments dans un univers U, la structure du problème ne dépend pas de la présence d'ensembles contenant des éléments. La même structure existe s'il y a deux ensembles avec une certaine relation binaire entre eux.

Étant donné un ensemble X, un ensemble Y, et une relation binaire R entre X et Y, une couverture exacte (généralisée) est un sous-ensemble X* de X tel que chaque élément de Y est R^-1-relié à exactement un élément de X*. Ici R^-1 est l'inverse de R.

En général, R^-1 restreinte à Y×X* est une fonction, c.a.d., chaque élément Y est R^-1-relié à exactement un élément de X* : l'unique élément de X* qui « couvre » l'élément particulier de Y.

De plus, si R est totalement gauche, c.a.d., si chaque élément de X est R-relié à au moins un élément de Y, alors R^-1 restreinte à Y×X* est une fonction surjective. (La condition dans le problème généralisé que R est totalement gauche correspond à la condition dans le problème standard que chaque ensemble dans est non-vide. Évidemment, cela ne fait pas de différence si un ensemble vide est une partie d'une couverture ou non.)

Dans la représentation matricielle du problème généralisé, la relation R est représentée par une matrice, les éléments de X sont représentés par les lignes de la matrice, et les éléments de Y sont représentés par les colonnes de la matrice. Alors, comme dans le problème standard, une couverture exacte (généralisée) est une sélection de lignes telles que chaque colonne possède 1 dans exactement une des lignes sélectionnées.

Le problème standard est un cas particulier du problème généralisé dans lequel l'ensemble X est une collection d'ensembles, l'ensemble Y est un univers U d'éléments, et la relation binaire R est la relation « contenue » entre les ensembles et les éléments. Alors R^-1 restreinte à Y×X* est une fonction des éléments vers les ensembles précisant l'unique ensemble dans la couverture qui contient l'élément précisé. De plus, si R est totalement gauche, c.a.d. si aucun ensemble n'est vide, alors R^-1 restreinte à Y×X* est une fonction surjective, c.a.d. chaque élément dans la couverture contient au moins un élément.

Exemple 4

La matrice dans l'exemple 3 ci-dessus peut être réinterprété pour représenter la relation binaire « est contenu dans » entre l'ensemble X = {1, 2, 3, 4, 5, 6} de 6 éléments et la collection Y = {A, B, C, D, E, F, G} de 7 ensembles :

• A = {1, 2}
• B = {5, 6}
• C = {4, 5}
• D = {1, 2, 3}
• E = {3, 4}
• F = {4, 5}
• G = {1, 3, 5, 6}

La même représentation matricielle comme dans l'exemple 3 s'applique ici, mais elle est étiquetée différemment :

	A	B	C	D	E	F	G
1	1	0	0	1	0	0	1
2	1	0	0	1	0	0	0
3	0	0	0	1	1	0	1
4	0	0	1	0	1	1	0
5	0	1	1	0	0	1	1
6	0	1	0	0	0	0	1

Comme dans l'exemple 3, une solution consiste à sélectionner les 2^e, 4^e et 6^e lignes de la matrice :

	A	B	C	D	E	F	G
2	1	0	0	1	0	0	0
4	0	0	1	0	1	1	0
6	0	1	0	0	0	0	1

Mais à la différence de l'exemple 3, l'interprétation ici montre que la solution est l'ensemble des éléments X* = {2, 4, 6} tel que chaque ensemble dans Y contient exactement un élément de X* :

• A = {1, 2}
• B = {5, 6}
• C = {4, 5}
• D = {1, 2, 3}
• E = {3, 4}
• F = {4, 5}
• G = {1, 3, 5, 6}

En d'autre termes, la solution est un ensemble intersectant exact. Vraiment, les problèmes de la couverture exacte et les problèmes d'ensemble intersectant exact sont duaux l'un de l'autre, c.a.d. essentiellement les mêmes.