Ensemble stable de poids maximal

Dans un graphe non orienté sans boucle ni arête multiple (cf. définitions dans théorie des graphes), noté G = (X, V), on recherche un ensemble stable de poids maximal (noté ESPM).

Un ensemble S inclus dans X est dit stable si et seulement si deux sommets distincts de S ne sont pas adjacents, c’est-à-dire, Γ(G) étant l'ensemble des sommets adjacents aux éléments de S, si et seulement si Γ(G) ∩ S = ∅.

• Un ensemble stable de G est maximal si et seulement s'il n'est contenu dans aucun autre ensemble stable de G.

• On associe à chaque sommet x de X un poids positif ou nul noté p(x) et on définit alors le poids P(S) d'un ensemble stable S par : $P(S)={\sum }_{x\in S}p(x)$.

Le problème de l'ESPM consiste à déterminer dans G un ensemble stable S₀ tel que $P(S_0)={\max }_{S\in S_G}P(S)$.

On notera qu'il existe un problème voisin qui est celui de l'ensemble stable de cardinal maximal (ESCM), qui se définit par :

• Soit S_G la famille des ensembles stables de G, le nombre de stabilité est : .

• Le problème de l'ESCM consiste à déterminer dans G un ensemble stable de cardinal α(G). Il s'agit d'un cas particulier d'ESPM où les poids sont égaux à 1.

• Le problème de l'ESPM, tout comme celui de l'ESCM, est NP-complet au sens de la théorie de la complexité.

• Une clique de G est un ensemble de sommets $C\subset X$, deux à deux adjacents, le graphe complémentaire de G est le graphe G' = (X,V') dont l'ensemble V' vérifie: $(x,y)\in V^{\prime }\equiv (x,y)\notin V$.

• Un support de G est un ensemble de sommets $T\subset X$ contenant au moins une extrémité de chaque arête de G.

• Un ESPM de G est une clique de poids maximal de G', T est un support de poids minimal si et seulement si X − T est un ESPM.

La recherche d'un ESPM dans un graphe permet la résolution des problèmes de maximisation de fonction pseudo-booléennes et de partitionnement.

• Étant donné une fonction pseudo booléenne f, on va construire un graphe en associant à chaque monôme un sommet du graphe en construction, de poids valant le coefficient dudit monôme. Une arête est générée entre deux sommets lorsque le produit booléen des monômes est nul. Ainsi le maximum de la fonction est égal au poids de l'ESPM du graphe.

Exemple :

Soit $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}$

Le graphe généré est le suivant :

L'ESPM (3,4) a pour poids 13, le maximum de la fonction vaut 13.

• Problème de partitionnement.

Exemple :

Chercher le minimum de 2x₁ + 3x₂ + 7x₃ + 4x₄ + 8x₅ avec les contraintes :

• x₄ + x₅ = 1
• x₂ + x₃ + x₄ = 1
• x₃ + x₄ = 1
• x₁ + x₂ + x₄ = 1

Le graphe généré est le suivant :

L'ESPM trouvé est (1, 3, 5).

La solution est

• x1 = 1
• x₂ = 0
• x₃ = 1
• x₄ = 0
• x₅ = 0