Conséquences algorithmiques du fait d'imposer des regroupements d'éléments dans certains problèmes d'optimisation de graphes

Lundi 14 octobre 2019, 14h, en salle B115

Christian Laforest (ISIMA, LIMOS, Université Clermont Auvergne)

Abstract :

[The talk will be in French but the slides will be in English]

J'exposerai des résultats récents que nous avons obtenus en travaillant sur des variantes de problèmes classiques
de graphes comme : vertex cover, dominant, arbre couvrant, couplage, etc.

Dans notre variante, certains des éléments (sommets ou arêtes) du graphe sont liés les uns aux autres : si l'un est choisi alors tous les autres qui lui sont liés doivent, obligatoirement, faire aussi partie de la solution. Chacun de ces "bloc" d'éléments est appelé une obligation.

Nous montrerons qu'avec cette contrainte il devient dans certains cas NP-complet de savoir s'il existe ou pas une solution. Dans d'autres cas il est possible de garder le même niveau d'approximation que pour la version classique.

Je présenterai (de manière très synthétique et rapide) les conséquences de la contrainte "inverse". Au lieu d'obliger des éléments à être ensemble, nous prendrons en compte le fait que certaines paires de sommets puissent être en conflit et ne puissent donc pas être présents tous les deux dans une même solution.
Nous avons montré que savoir s'il existe ou pas une solution (évitant les conflits) devient NP-complet, même pour des graphes et des conflits très "simples".