Groupe d’études et de recherche en analyse des décisions

Transformations de graphes et réductions pseudobooléennes

Dominique De Werra École Polytechnique Fédérale de Lausanne (EPFL), Suisse

Des transformations de graphes ont été élaborées soit pour réduire d’une quantité donnée le nombre de stabilité d’un graphe, soit pour diminuer le nombre d’arêtes ou de sommets sans changer le nombre de stabilité. Certaines de ces transformations ont été inspirées par des formulations pseudobooléennes du problème de la recherche d’un ensemble stable de taille maximum.

Il est apparu que certaines de ces transformations ont des liens très directs avec des opérations de fusion de sommets utilisées pour les graphes parfaits.

Nous examinerons certaines de ces réductions dont celle dite de l’aimant et mettrons en évidence des connexions avec des extensions des couples de sommets liés uniquement par des chaines induites de longueur paire (de tels sommets sont appelés amis).

Des questions ouvertes sur l’interprétation des réductions dans le cas de classes particulières de graphes parfaits seront présentées.