Problème du stable maximum

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Exemple : organisation d'un dîner.

En informatique théorique, le problème du stable maximum ou maximum independent set problem en anglais, est un problème d'optimisation qui consiste étant donné un graphe non orienté à 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.

Exemple[modifier | modifier le code]

Prenons l'exemple du graphe donné à droite. Il représente l'organisation d'un dîner[1] où les invités potentiels sont Anne, Bernard, Chloé, Daniel, Édouard et Françoise.Les sommets sont les invités potentiels. Mais Anne et Chloé ne s'apprécient pas, Anne et Daniel ne s'apprécient pas, Chloé et Bernard ne s'apprécient pas, etc. Il y a une arête entre deux personnes qui ne s'apprécient pas. L'objectif est d'inviter le maximum de personnes qui s'apprécient mutuellement. Il s'agit donc de trouver un stable maximum.

Résolution exacte[modifier | modifier le code]

Complexité[modifier | modifier le code]

Le problème de décision associé au problème du stable maximum est le suivant : étant donné un graphe G et un entier k, décider si un stable de taille supérieur à k existe dans un graphe G. Le problème de décision associé au problème du stable maximum et le problème de décision associé au problème de la clique maximale sont interréductibles : il existe un stable de taille supérieur à k dans un graphe G ssi il existe une clique de taille supérieure à k existe dans le graphe complémentaire de G (obtenu en retirant les arêtes présentes dans le graphe d'origine et en ajoutant les arêtes absentes dans le graphe d'origine). Ainsi, le problème de décision associé au problème du stable maximum est NP-complet au sens de la théorie de la complexité comme le problème de la clique maximum, et fait partie des 21 problèmes NP-complets de Karp[2],[3].

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[4] 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)[5].

Approximation[modifier | modifier le code]

Le problème est aussi difficile à approximer. Pour tout , il est NP-difficile d'approximer la taille du stable maximum avec un ratio [6]. En particulier le problème n'est pas dans la classe APX.

Problèmes proches[modifier | modifier le code]

Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
Question book-4.svg
Cette section ne cite pas suffisamment ses sources (indiquez la date de pose grâce au paramètre date).
Pour l'améliorer, ajoutez des références vérifiables [Comment faire ?] ou le modèle {{Référence nécessaire}} sur les passages nécessitant une source.

Le problème est équivalent au problème de la clique maximum, puisqu'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 ). 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 , c'est-à-dire lorsque seul les troisième et quatrième monômes valent 1. Il existe une variante pondérée du problème du stable maximum consiste où chaque sommet possède à poids et le but est de trouver un stable de poids maximal.

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

  1. (en) « Complexity theory à la Technische Üniverstät München », p. 23
  2. Sous le nom CLIQUE.
  3. (Karp 1972)
  4. (Rose, Tarjan et Lueker 1976)
  5. (Fulkerson et Gross 1965)
  6. David Zuckerman, « Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number », Theory of Computing, vol. 3, no 1,‎ , p. 103-128

Bibliographie[modifier | modifier le code]

  • (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Complexity of Computer Computations, Plenum, (lire en ligne), p. 85-103
  • (en) Donald J. Rose, R.Endre Tarjan et George S. Lueker, « Algorithmic aspects of vertex elimination on graphs. », SIAM Journal on Computing, vol. 5,‎ , p. 266-283 (ISSN 0097-5397 et 1095-7111, DOI 10.1137/0205021)
  • Delbert R Fulkerson et Oliver A Gross, « Incidence matrices and interval graphs », Pacific J. Math, vol. 15, no 3,‎
  • 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