Problème du stable maximum

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, 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.

Le problème est aussi difficile à approximer. Pour tout ${\displaystyle \epsilon }$, il est NP-difficile d'approximer la taille du stable maximum avec un ratio ${\displaystyle n^{1-\epsilon }}$[6]. En particulier, si P est différent de NP le problème n'est pas dans la classe APX.

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.

• Le problème de couverture par sommets (i.e. le problème du transversal) : 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 ${\displaystyle f(x_{1},x_{2},x_{3})=3x_{1}{\overline {x_{2}}}+4x_{1}{\overline {x_{2}}}x_{3}+6x_{1}{\overline {x_{3}}}+7x_{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 :

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 ${\displaystyle x_{1}=0,x_{2}=0,x_{3}=1,x_{4}=1}$, 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.

• (en) Richard M. Karp, « Reducibility Among Combinatorial Problems », dans Raymond E. Miller et James W. Thatcher, Complexity of Computer Computations, Plenum, 1972 (ISBN 978-1-4684-2003-6, DOI 10.1007/978-1-4684-2001-2_9, 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,‎ 1976, 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, n^o 3,‎ 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