Une nouvelle méthode pour obtenir des algorithmes d’énumération à délai et espace polynomiaux

Nous nous intéresserons durant cet exposé à des problèmes d’énumération, c’est-à-dire aux problèmes consistant à lister toutes les solutions d’un problème donné. “Proximity search” est une méthode relativement récente permettant d’obtenir des algorithmes à délai polynomial (pour lesquels le temps entre la sortie de deux solutions consécutives est polynomial en la taille de l’instance) pour énumérer les sous-ensembles maximaux par inclusion vérifiant une certaine propriété. Bien que cette méthode soit puissante, elle nécessite cependant l’utilisation d’un espace exponentiel, et les techniques classiques en énumération permettant de réduire cet espace ne s’appliquent pas dans ce cadre. Nous présenterons une nouvelle méthode permettant d’obtenir un espace polynomial, tout en utilisant “proximity search”. Nous l’utiliserons notamment pour montrer qu’on peut énumérer les complétions cordales minimales d’un graphe ou de manière équivalente les décompositions arborescentes minimales d’un graphe avec un délai et un espace polynomiaux.