Ensemble stable de poids maximal

Le lecteur est renvoyé à l'article théorie des graphes pour une introduction aux graphes et à l'article Lexique de la théorie des graphes pour les définitions élémentaires.

Le problème du stable maximum est parfaitement équivalent à celui de la clique maximum et très proche du transversal minimum.

Définition du problème

Le problème du stable maximum se pose dans un graphe que l'on peut considérer simple puisque son éventuelle orientation ou la présence d'arêtes multiples ne jouent aucun rôle ici (on peut se débarrasser des sommets incidents aux boucles car ils n'appartiennent à aucun stable du graphe).

Soit G un graphe simple, et soit S un sous-ensemble stable de l'ensemble X des sommets de G.

• S est maximal (par rapport à l'inclusion) s'il n'est contenu dans aucun autre ensemble stable de G.
• S est de cardinalité maximum si sa cardinalité est supérieure ou égale à la cardinalité de tout autre stable de G.

Une cardinalité maximum implique maximal, mais non l'inverse. Le nombre de stabilité de G, noté α(G), est la cardinalité d'un stable maximum. Le problème du stable maximum consiste à déterminer α(G) étant donné un graphe G. Ce problème est NP-complet au sens de la théorie de la complexité.

Munissons maintenant G d'une pondération en associant à chaque sommet x de X un réel p(x) appelé le poids de x. Le poids P(Y) d'un sous-ensemble Y de X est alors égal à la somme des poids des sommets de Y.

• S est de poids maximum si le poids de S est supérieur ou égal au poids de tout autre stable de G.

Le problème du stable maximum dans un graphe pondéré consiste à déterminer le poids maximum d'un stable de G. À moins que la fonction p ne soit positive, un stable maximum n'est pas nécessairement maximal dans les graphes pondérés.

Problèmes proches

Puisque le problème du stable maximum est NP-dur, tous les problèmes de cette classe peuvent s'exprimer comme un problème de stable maximum (et vice versa). Toutefois, certains problèmes, comme ceux que nous présentons ci-dessous, lui sont plus directement relié.

• Problème de la clique maximum : Il s'agit de déterminer le poids maximum d'une clique de G. L'équivalence est totale, même au niveau des algorithmes d'approximation, il suffit de reformuler le problème dans le graphe complémentaire de G.

• Problème du transerval minimum (ou encore de la couverture minimum par des sommets): Il s'agit de déterminer un transversal minimum. L'équivalence vient du fait que le complémentaire d'un transversal de G (par rapport à l'ensemble X) est un stable de G. Attention ce problème n'est pas équivalent au sens de l'approximation.

Les problèmes suivants ne nécessitent qu'une simple transformation pour être reformulés comme un problème de stable maximum:

• Problème de la maximisation d'une fonction pseudo booléenne (par exemple la fonction ). L'équivalence passe par la construction d'un graphe auxiliaire. Associons à chaque monôme de la fonction un sommet du graphe, auquel on donne un poids égal au coefficient du monôme. Relions deux sommets par une arête lorsque le produit booléen des deux monômes correspondants est nul. Ainsi le maximum de la fonction est égal au poids maximum d'un stable du graphe. Avec la fonction f donnée en exemple, on obtient le graphe suivant :

Ici le stable maximum est composé des sommets 3 et 4 et a pour poids 13, le maximum de f vaut 13 (il est atteint par x₁ = 0,x₂ = 0,x₃ = 1,x₄ = 1, c'est à dire lorsque seul les troisième et quatrième monômes valent 1.

Référence

B Ambert et P Castéra, Réalisation d'un algorithme efficace pour la détermination en ensemble stable de poids maximal d'un graphe, Mémoire d'ingénieur de l'Institut d'Informatique d'Entreprise (IIE-CNAM), Paris 1981