Ensemble intersectant

En informatique théorique, le problème de l'ensemble intersectant (en anglais Hitting Set Problem) est un problème NP-complet de la théorie combinatoire des ensembles. Il fait partie des 21 problèmes NP-complets décrits par Richard M. Karp, en 1972, dans son célèbre article Reducibility Among Combinatorial Problems^[1].

Description

Étant donné une famille S de sous-ensembles d'un « univers » U, on cherche un sous-ensemble H de U (le hitting set) qui contient au moins un élément de chaque sous-ensemble de la famille S. De plus, il est demandé que le nombre d'éléments de H n'excède pas une valeur k donnée.

Définition formelle

On se donne

• une collection d'ensembles ${\displaystyle \{S_{1},S_{2},\ldots ,S_{n}\}}$ dont chacun ${\displaystyle S_{i}}$ est un sous-ensemble d'un ensemble donné ${\displaystyle U}$ et
• un entier positif ${\displaystyle k\leq \vert U\vert }$.

Le problème consiste à déterminer s'il existe un sous-ensemble ${\displaystyle H}$ de ${\displaystyle U}$ tel que ${\displaystyle |H|\leq k}$ et ${\displaystyle H\cap S_{i}\neq \emptyset }$ pour ${\displaystyle i\in \{1,2,\dots n\}}$.

Complexité

On peut démontrer que le problème de l'ensemble intersectant est NP-difficile, par réduction du problème de couverture par sommets (Vertex cover).

Preuve: Soit ${\displaystyle \langle G,k\rangle }$ une instance du problème de couverture par sommets et soit ${\displaystyle G=(V,E)}$. On pose ${\displaystyle U=V}$ et on définit ${\displaystyle S}$ comme la famille des ensembles ${\displaystyle \{u,v\}}$ pour toute arête ${\displaystyle (u,v)\in E}$. On montre que S admet un ensemble intersectant H de taille k si et seulement si G possède une couverture par sommets C de taille k :

(${\displaystyle \Rightarrow }$) Si S admet un ensemble intersectant H de taille k, alors comme H contient une extrémité de chaque arête, l'ensemble C = H est une couverture par sommets de taille k.

(${\displaystyle \Leftarrow }$) Si G possède une couverture par sommets C de taille k, alors pour chaque arête ${\displaystyle (u,v)}$ on a ${\displaystyle u\in C}$ ou ${\displaystyle v\in C}$ (ou les deux). En posant H = C, on obtient un ensemble intersectant de taille k.

On peut aussi montrer que le problème de l'ensemble intersectant est équivalent au problème de couverture par ensembles. Pour s'en convaincre, on observe qu'une instance du problème de couverture par ensembles peut être vue comme un graphe biparti, où les ensembles sont représentés par les sommets de la colonne gauche, et les éléments de l'univers par les sommets de la colonne droite. Une arête représente l'appartenance de l'élément (à droite) à l'ensemble (à gauche). L'objectif est de trouver une famille de taille minimale de sommets de gauche qui couvre tous les sommets de droite. Dans le problème de l'ensemble intersectant, l'objectif est au contraire de couvrir les sommets de gauche en utilisant un ensemble de sommets de droite de taille minimale. La conversion de l'un des problèmes en l'autre se fait donc en échangeant les deux ensembles de sommets.

Propriétés

Étant donné la similitude entre le problème de l’ensemble intersectant d'une part, le problème de la couverture par sommets et le problème de la couverture par ensembles, toutes les propriétés de ces deuxièmes problèmes se traduisent directement en des propriétés analogues du premier. C'est pourquoi la littérature abondante concernant les problèmes de la couverture par sommets et la couverture par ensembles concerne également le problème de l'ensemble intersectant.

Notes et références

1. (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, 1972 (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103

Bibliographie

• (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, 1972 (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, lire en ligne), p. 85-103
• (en) Michael Garey et David S. Johnson, Computers and Intractability : A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979 (ISBN 0-7167-1045-5)

Lien externe

• (en) Viggo Kann, « Minimum Hitting Set », sur A compendium of NP optimization problems, 20 mars 2000 (consulté le 6 août 2014)