Ensemble dominant

Un code identifiant d'un graphe est un sous-ensemble C de sommets de G qui est à la fois un code couvrant et un code séparateur. Ce sous-ensemble C 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 ${\displaystyle N(v)\cap C}$. On notera cet ensemble ${\displaystyle L(v,C)}$ ou ${\displaystyle L(v)}$.

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

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.

(${\displaystyle \Rightarrow }$) D est un ensemble dominant de G' de taille k. On peut alors construire un ensemble D' de taille k en remplaçant tous les sommets de D qui ne figurent pas dans le graphe de départ G par l'un de leurs 2 voisins qui eux sont des sommets de G et de G' . Ainsi, tout arc de G concerne un sommet de D' . D' est donc une couverture des sommets de G de taille k.

(${\displaystyle \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.

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