Algorithmes d'approximation pour l'ensemble indépendant maximum sur des classes spéciales de graphiques

Nous savons que l'ensemble indépendant maximum (MIS) est difficile à estimer dans un facteur pour tout ϵ $n^{1-\epsilon}$ moins que P = NP. Quelles sont certaines classes spéciales de graphiques pour lesquelles de meilleurs algorithmes d'approximation sont connus?$\epsilon > 0$

Quels sont les graphes pour lesquels les algorithmes polynomiaux sont connus? Je sais que pour des graphiques parfaits, cela est connu, mais existe-t-il d'autres classes de graphiques intéressantes?

Il y a une liste vraiment impressionnante de toutes les classes de graphes connues qui ont des algorithmes non triviaux pour MIS: voir cette entrée sur le site Web des classes de graphes.

Je n'ai pas une bonne vue d'ensemble de ce problème, mais je peux donner quelques exemples. Un algorithme d'approximation simple serait de trouver un certain ordre des nœuds et de sélectionner avidement les nœuds à faire dans l'ensemble indépendant si aucun de ses voisins précédents n'a été sélectionné dans l'ensemble indépendant.

Si le graphique présente une dégénérescence utilisation de l'ordre de dégénérescence donnera une approximation d . donc pour les graphes de dégénérescence n 1 - $d$$d$$n^{1-\epsilon}$ nous avons une assez bonne approximation.

Il existe quelques autres techniques d'approximation qui fonctionnent aussi, mais je ne les connais pas bien. Voir: http://en.wikipedia.org/wiki/Baker%27s_technique et http://courses.engr.illinois.edu/cs598csc/sp2011/Lectures/lecture_7.pdf

Pour les algorithmes polynomiaux résolvant les problèmes exactement Le lien que Suresh a donné est le meilleur. Les classes graphiques les plus intéressantes sont difficiles à dire.

$k$$O(2^k n)$$k$$O(\log n)$

Pour la classe des graphiques planaires cubiques, cet article, Un algorithme d'approximation pour le problème d'ensemble indépendant maximum dans les graphiques planaires cubiques par Elarbi Choukhmane et John Franco, donne un algorithme d'approximation polynomiale du temps. Le facteur d'approximation de leur algorithme est 6/7.

Je n'ai pas vérifié les réponses ci-dessus, donc mes excuses s'il y a un chevauchement. Voici un cas spécial où vous pouvez le résoudre exactement en temps polynomial. Si votre graphique G est un graphique linéaire , exécutez un algorithme de temps polynomial pour trouver le graphique racine H, puis recherchez une correspondance maximale dans H.

Dans les graphiques d'intersection géométrique, il existe plusieurs approximations intéressantes, PTAS et algorithmes exacts sous-exponentiels. Voir l'article Wikipédia Ensemble disjoint maximum pour une enquête.