Ensemble dominant

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes, un ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D possède au moins une arête commune avec un sommet de D. Le problème d'ensemble dominant est de déterminer, en fonction de G et d'un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet.

Un graphe avec trois exemples d'ensembles dominants (constitués des sommets rouges).

Définitions[modifier | modifier le code]

Un ensemble dominant (ou dominating set en anglais) d'un graphe G = ( S, A ) est un sous-ensemble D de l'ensemble S des sommets tel que tout sommet qui n'appartient pas à D possède au moins une arête commune avec un sommet de D.

Le problème d'ensemble dominant est de déterminer, en fonction de G et d'un entier naturel k, si G possède un ensemble dominant d'au plus k sommets. Ce problème est NP-complet.

Exemple, remarques et propriétés combinatoires[modifier | modifier le code]

L'ensemble S de tous les sommets est toujours dominant.

Code identifiant[modifier | modifier le code]

Un code identifiant d'un graphe est un sous-semble C de sommets de G qui est à la fois un code couvrant et un code séparateur est appelé un code identifiant de G. Tous les sommets du graphe G sont donc couverts et séparés. On appelle pour chaque sommet v ensemble identifiant l’ensemble N(v)\cap C. On notera cet ensemble L(v, C) ou L(v).

On a donc C qui est un code identifiant de G si et seulement si l’application : V\rightarrow\; L(v, C) est une injection dont l’image ne contient pas l’ensemble vide.

Complexité du problème[modifier | modifier le code]

Le problème d'ensemble dominant a été prouvé NP-complet par réduction avec le problème de couverture par sommets. Les deux problèmes sont similaires, la différence étant que le premier concerne des arcs alors que le second concerne les sommets.

Le problème de l'ensemble dominant est utilisé lui-même pour montrer la difficulté d'autres problèmes, comme le problème k-centre métrique[1].

Couverture par sommets vers ensemble dominant[modifier | modifier le code]

Les couvertures de sommets du graphe G correspondent aux ensembles dominants du graphe G' construit à partir de G

Soit <G, k> une instance du problème de couverture de sommets. On construit (cf figure ci-contre) un nouveau graphe G' , en ajoutant à G de nouveaux sommets, pour représenter les arcs du graphe initial G. Précisément, pour tout arc <v, w> de G, ajoutons un sommet vw et les arcs <v, vw> et <w,vw>.

Montrons qu'alors, G' a un ensemble dominant D de taille k si et seulement si G a une couverture de sommets C de taille k.

(\Rightarrow) D est un ensemble dominant de G' de taille k. Donc, tout arc de G' concerne un sommet de D. D est donc une couverture des sommets de G de taille k.

(\Leftarrow) C est une couverture par sommets de G de taille k, donc les nouveaux et les anciens sommets sont dominés par k sommets.

Algorithmes[modifier | modifier le code]

Résolution exacte[modifier | modifier le code]

Approximation[modifier | modifier le code]

La version « optimisation » du problème, qui consiste à trouver un ensemble dominant D tel que |D| soit minimum, est approximable. Pour être plus précis, il est approximable avec un facteur  1 + \log |D|, comme cas particulier du problème de couverture par ensembles[2]. Cependant, il n'est pas approximable à une distance c \log |D| pour un c > 0[2].

Notes et références[modifier | modifier le code]

  1. (en) Vijay Vazirani, Approximation algorithms, Springer Verlag,‎ 2001 (puis 2003), 380 p. (ISBN 978-3-540-65367-7), chap. 5 (« k-center »).
  2. a et b (en) Minimum dominating set, une page du Compendium of NP optimization problems de P. Crescenzi et V. Kann

Bibliographie[modifier | modifier le code]