Résumé :

Nous allons explorer la complexité algorithmique induite par l’introduction d’obligations dans des problèmes classiques de graphes. Ces obligations, définies comme des contraintes imposant la présence collective de certains éléments dans une solution, modifient la nature des solutions admissibles.
À travers deux problèmes classiques — l'ensemble dominant indépendant et des problèmes de tournées —, nous montrons que ces obligations rendent de nombreux problèmes NP-complets, y compris sur des graphes très simples (il reste heureusement des cas limites où des solutions restent polynomiales).