Problème du stable maximum

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

En informatique théorique, le problème du stable maximum ou maximum independent set problem en anglais, consiste étant donné un graphe à trouver un stable de cardinal maximum, c'est-à-dire un sous-ensemble de sommets du graphe, le plus grand possible, tel que les éléments de ce sous-ensemble ne soient pas voisins.

Définitions[modifier | modifier le code]

Un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents Un stable est maximum si tout les autres stables sont de même taille ou plus petits.

Une variante du problème consiste à associé un poids à chaque sommets et à maximiser le poids total du stable.

Lien avec le problème de la clique maximum et problèmes proches[modifier | modifier le code]

Cette section ne cite pas suffisamment ses sources. Pour l'améliorer, ajouter en note des références vérifiables ou les modèles {{Référence nécessaire}} ou {{Référence souhaitée}} sur les passages nécessitant une source.

Le problème est équivalent au problème de la clique maximum, puisque un stable est une clique dans le graphe complémentaire. Ainsi ces deux problèmes ont la même complexité. Cependant quand on réduit l'ensemble des graphes d'entrée (par exemple on cherche un stable maximum pour des graphes cordaux), cette équivalence n'est plus aussi pertinente puisque le graphe complémentaire peut ne pas appartenir à la classe.

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  f(x_1,x_2,x_3) =  3 x_1\overline{x_2} + 4 x_1\overline{x_2}x_3 + 6 x_1\overline{x_3}+ 7 x_2\overline{x_3}). 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 :
ESPM equiv bool.png
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_1=0, x_2=0, x_3=1, x_4=1 , c'est-à-dire lorsque seul les troisième et quatrième monômes valent 1.

Complexité[modifier | modifier le code]

Ce problème hérite de la complexité du problème de la clique maximum. Il est NP-complet au sens de la théorie de la complexité, et fait partie des 21 problèmes NP-complets de Karp[1],[2].

Problème restreint à certaines classes de graphes[modifier | modifier le code]

On peut étudier le problème du stable maximum sur des classes de graphe particulière. Par exemple le problème peut être résolu en temps linéaire sur les graphes cordaux[3] mais reste NP-complet sur les graphe de boxicité (en) 2 (i.e les graphes représentant des intersections de rectangles dans le plan, alignés selon les axes)[4].

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

  1. Sous le nom CLIQUE.
  2. (Karp 1972)
  3. (Rose, Tarjan et Lueker 1976)
  4. (Fulkerson et Gross 1965)

Bibliographie[modifier | modifier le code]

  • 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