Jean-Marie Le Bars (GREYC)

Le noyau d’un graphe est un sous-ensemble de l’ensemble des sommets à la fois stable et dominant.

Le problème de décider si un graphe possède un noyau est NP-complet, mais cela ne garantit pas qu’il est facile d’obtenir des distributions naturelles produisant des instances difficiles (les algorithmes connus ne sont pas polynomiaux).

Nous nous intéresserons aux distributions obtenues avec le célèbre modèle d’Erdös et Rényi, le modèle G ( n , p ) : n est le nombre de sommets et p la probabilité d’arc : on met un arc entre deux sommets avec la probabilité p , où p est fixé ou fonction de n.

Nous verrons que les tailles possibles des noyaux d’un graphe de G ( n , p ) varient fortement selon la valeur de p et que le cas p = c ⁄ n semble fournir les instances les plus difficiles.