Voir la source de Problème du stable maximum

[[Fichier:Stable maximum.svg|vignette|Exemple : organisation d'un dîner.]]
En [[informatique théorique]], le '''problème du stable maximum''' ou '''''{{Langue|en |texte=maximum independent set problem}}''''' en anglais, est un problème d'[[Optimisation (mathématiques) |optimisation]] qui consiste étant donné un [[graphe non orienté]] à trouver un [[stable (théorie des graphes)|stable]] de [[Cardinal (mathématiques)|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 ==
Prenons l'exemple du graphe donné à droite. Il représente l'organisation d'un dîner<ref>{{Lien web|langue=anglais|titre = Complexity theory à la Technische Universität München |description=p. 23 | url=https://www7.in.tum.de/um/courses/complexity/SS10/slides/lecture1.pdf|date=}}</ref> où les invités potentiels sont Anne, Bernard, Chloé, Daniel, Édouard, Françoise et Guillaume. 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 ==
=== Complexité ===
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érieure à ''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 (théorie des graphes)|clique maximale]] sont [[Réduction polynomiale|interréductibles]] : il existe un stable de taille supérieure à ''k'' dans un graphe G si et seulement si il existe une [[clique (théorie des graphes)|clique]] de taille supérieure à ''k'' 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é (informatique théorique)|théorie de la complexité]], comme le [[problème de la clique|problème de la clique maximum]], et fait partie des [[21 problèmes NP-complets de Karp]]<ref>Sous le nom ''CLIQUE''.</ref>{{,}}<ref>{{harv|Karp 1972}}</ref>.

=== Problème restreint à certaines classes de graphes ===
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]]<ref>{{harv|Rose|Tarjan|Lueker|1976}}</ref> mais reste NP-complet sur les graphe de {{lien|fr=boxicité|trad=boxicity}} 2 (''i.e'' les graphes représentant des intersections de rectangles dans le plan, alignés selon les axes)<ref>{{harv|Fulkerson|Gross|1965}}</ref>.

== Approximation ==
Le problème est aussi difficile à [[algorithme d'approximation|approximer]]. Pour tout <math>\epsilon</math>, il est [[NP-difficile]] d'approximer la taille du stable maximum avec un ratio <math>n^{1-\epsilon}</math><ref>
{{article
 |auteur   = David Zuckerman
 |titre     = Linear Degree Extractors and the Inapproximability of Max Clique and Chromatic Number
 |périodique   = Theory of Computing
 |volume    = 3 |numéro    = 1 |passage     = 103-128
 |année      = 2007}}</ref>. En particulier, si P est différent de NP le problème n'est pas dans la classe [[APX (complexité)|APX]].

== Problèmes proches ==
{{section à sourcer|date=novembre 2013}}

Le problème est équivalent au problème de la [[clique (théorie des graphes)|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 [[graphe cordal|graphes cordaux]]), cette équivalence n'est plus aussi pertinente puisque le graphe complémentaire peut ne pas appartenir à la classe.

* Le '''[[problème de couverture par sommets]]''' (i.e. le problème du transversal) :  Il s'agit de déterminer un [[Lexique de la théorie des graphes#T|transversal]] minimum. {{référence souhaitée|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 [[Algèbre de Boole (logique)|fonction pseudo booléenne]] (par exemple la fonction <math> 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}</math>). 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 :
::[[Image: ESPM equiv bool.png| 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 <math> x_1=0, x_2=0, x_3=1, x_4=1 </math>, c'est-à-dire lorsque seuls les troisième et quatrième monômes valent 1. Il existe une variante pondérée du problème du stable maximum où chaque sommet possède un poids et le but est de trouver un stable de poids maximal.

== Notes et références ==
<references />

== Bibliographie ==
* {{Reducibility Karp 1972}}
* {{article
 |nom1 = Rose
 |prénom1 = Donald J.
 |nom2 = Tarjan
 |prénom2 = R.Endre
 |lien auteur2 = Robert Tarjan
 |nom3 =Lueker
 |prénom3 = George S. 
 |titre = Algorithmic aspects of vertex elimination on graphs.
 |journal = SIAM Journal on Computing
 |issn = 0097-5397
 |issn2 = 1095-7111
 |volume = 5
 |passage = 266-283
 |année = 1976
 |langue = en 
 |doi = 10.1137/0205021
}}
* {{article
 | nom1 = Fulkerson
 | prénom1 = Delbert R
 | lien auteur1 = Delbert Fulkerson
 | nom2 = Gross
 | prénom2 =  Oliver A 
 | titre = Incidence matrices and interval graphs
 | journal = Pacific J. Math
 | volume = 15
 | numéro = 3 
 | année = 1965
}}

* 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

{{Portail|Informatique théorique}}

[[Catégorie:Problème NP-complet|stable maximum]]