Ensemble dominant

Étant donné un graphe non orienté , un sous-ensemble de sommetsensemble dominant si pour chaque sommet

Tout graphe possède au moins un ensemble dominant : siD est un ensemble dominant, puisqu'il n'y a pas de sommetnombre de domination de est défini comme suit :

Le problème de la domination a été étudié dès les années 1950, mais le rythme des recherches sur ce sujet s'est considérablement accéléré au milieu des années 1970. En 1972, Richard Karp a démontré que le problème de la couverture d'ensembles est NP-complet . Cette démonstration a eu des implications immédiates pour le problème de l'ensemble dominant, car il existe des bijections directes entre les sommets et les ensembles, ainsi qu'entre les arêtes et les intersections non disjointes. Cela a également prouvé que le problème de l'ensemble dominant est NP-complet .

Le problème de la couverture d'ensembles est un problème NP-difficile bien connu ; sa version décisionnelle figurait parmi les 21 problèmes NP-complets de Karp . Il existe une paire de L-réductions polynomiales entre le problème de l'ensemble dominant minimal et le problème de la couverture d'ensembles . Ces réductions ( voir ci-dessous ) montrent qu'un algorithme efficace pour le problème de l'ensemble dominant minimal est également efficace pour le problème de la couverture d'ensembles, et réciproquement. De plus, les réductions préservent le rapport d'approximation : pour tout α, un algorithme polynomial pour le problème de la couverture d'ensembles, et réciproquement. Les deux problèmes sont en fait Log-APX-complets .

L'approximabilité de la couverture d'ensembles est également bien comprise : un facteur d'approximation logarithmique peut être trouvé à l'aide d'un algorithme glouton simple , et trouver un facteur d'approximation sous-logarithmique est NP-difficile. Plus précisément, l'algorithme glouton fournit une approximation d'un facteur V | d'un ensemble dominant minimal, et aucun algorithme polynomial ne peut atteindre un facteur d'approximation meilleur que V | pour un certain , sauf si P = NP .

Réductions L

Les deux réductions suivantes montrent que le problème de l'ensemble dominant minimal et le problème de la couverture d'ensembles sont équivalents sous les L-réductions : étant donné une instance d'un problème, nous pouvons construire une instance équivalente de l'autre problème.

De l'ensemble dominant à la couverture de l'ensemble

Étant donné un graphe avec construisez une instance de couverture d'ensemble comme suit : l' univers , et la famille de sous-ensembles est telle que consiste en le sommet dans est un ensemble dominant pour : v ∈ D } est une solution admissible du problème de couverture d'ensembles, avec C | = | D | . Réciproquement, si : v ∈ D } est une solution admissible du problème de couverture d'ensembles, alors , avec D | = | C | .

Par conséquent, la taille d'un ensemble dominant minimal pour efficace pour les ensembles dominants minimaux.

Par exemple, étant donné le graphe et les sous-ensembles et Dans cet exemple, est un ensemble dominant pour Par exemple, le sommet est dominé par le sommet ∈ et l'élément inclus dans l'ensemble

De la couverture du décor à la domination du décor

Soit une instance du problème de couverture d'ensembles avec l'univers : i ∈ I } ; on suppose que sont disjoints. Construisons un graphe comme suit : l'ensemble des sommets est , il existe une arête entre chaque paire , et il existe également une arête pour chaque et </sub> . Autrement dit, est une clique et : i ∈ D } est une solution admissible du problème de couverture d'ensembles pour un certain sous-ensemble , alors , avec D | = | C | : Premièrement, pour chaque il existe un tel que , et par construction, sont adjacents dans est dominé par doit être non vide, chaque est adjacent à un sommet de un ensemble dominant pour tel que X | ≤ | D | et : il suffit de remplacer chaque par un voisin de : i ∈ X } est une solution admissible du problème de couverture d'ensembles, avec C | = | X | ≤ | D | .

L'illustration de droite montre la construction pour et

Dans cet exemple, est une couverture d'ensemble ; cela correspond à l'ensemble dominant

est un autre ensemble dominant du graphe , on peut construire un ensemble dominant inférieur ou égal à L'ensemble dominant

Un ensemble dominant indépendant est un ensemble dominant qui est également un ensemble indépendant , ou, de manière équivalente, un ensemble indépendant maximal . Le nombre de domination indépendantePour tout graphe est un ensemble qui domine tout ensemble indépendant denombre de domination de l'indépendance

Un ensemble dominant connexe est un ensemble dominant qui est également connexe .

Un ensemble dominant total est un ensemble de sommets tel que tous les sommets du graphe, y compris les sommets appartenant à l'ensemble dominant lui-même, ont un voisin appartenant à l'ensemble dominant. Autrement dit : pour chaque sommetnombre de domination totale

Un ensemble d'arêtes dominant est un ensemble d'arêtes (paires de sommets) dont l'union est un ensemble dominant ; un tel ensemble peut ne pas exister (par exemple, un graphe avec un ou plusieurs sommets et aucune arête ne le possède pas). S'il existe, alors l'union de toutes ses arêtes est un ensemble dominant total. Par conséquent, la taille minimale d'un ensemble d'arêtes dominant est au moins .

En revanche, un ensemble dominant les arêtes est un ensemble

Un ensemble voisins dans l'ensemble (un ensemble dominant standard est un ensemble 1-dominant). De même, un ensemble voisins dans l'ensemble (un ensemble dominant total est un ensemble 1-dominant). Une approximation à + log n ) d'un ensemble -dominant (par exemple, l'ensemble de tous les sommets) ; mais seuls les graphes de degré minimal admettent un ensemble -dominant, un ensemble fois plus grand qu'un ensemble d'un ensemble tel que pour chaque sommetnombre de domination fractionnaire

Un ensemble à étoiles dominantes est un sous-ensemble

Une partition domatique est une partition des sommets en ensembles dominants disjoints. Le nombre domatique est la taille maximale d'une partition domatique.

Un ensemble dominant éternel est une version dynamique de la domination dans laquelle un sommet

Un ensemble dominant efficace (également appelé ensemble ed ou ensemble dominant parfait indépendant ) est un ensemble dominant possédant la propriété supplémentaire que chaque sommet du graphe est dominé par exactement un sommet de l'ensemble.

Un ensemble dominant romain est défini par une fonction dominante romaine , qui attribue à chaque sommet une valeur issue de cet ensemble.nombre de domination romaine

Un ensemble dominant global est un ensemble dominant d'un graphe.nombre de domination mondiale

Un ensemble dominant certifié est un ensemble dominant dans lequel chaque sommet de l'ensemble a soit zéro, soit au moins deux voisins extérieurs à l'ensemble. Le nombre de domination certifiésommet de support faible (en particulier, lorsque

Un ensemble dominant apparié d'un graphenombre de domination appariée

D'autres variantes incluent

• ensemble dominant restreint,
• ensemble dominant sécurisé,
• ensemble dominant triplement connexe,
• ensemble dominant signé,
• moins l'ensemble dominant, et
• ensemble dominant amical.