Ensemble stable maximal

Soit $G = (S, A)$ un graphe non orienté muni d'une pondération $p$ un sous-ensemble $K$ de $S$ est un ensemble stable si

$$\forall a = (e, e^\prime) \in A, e \not \in K\ ou\ e^\prime \not \in K$$

Le poids de cet ensemble stable est

$$\sum_{s \in K} p(s)$$

Le problème de l'ensemble stable maximal est défini comme suit :

• données : un graphe $G$, une pondération $p$
• question : trouver le sous-ensemble $K$ de poids maximal parmi les ensembles stables de $G$.

Ce problème est NP-Complet dans le cas général, polynomial si le graphe est un arbre ou est biparti