De nombreux problèmes d’optimisation ayant des applications en production ou en informatique sont définis à partir d’un graphe orienté sans circuit (DAG). C’est notamment le cas des problèmes d’ordonnancement de tâches soumises à des contraintes de précédence et exécutées sur un nombre limité de machines, des problèmes d'équilibrage de ligne d'assemblage, ainsi que de certains problèmes de numérotation topologique, dans lesquels on cherche à optimiser des fonctions telles que la Bandwidth, la Cutwidth ou le Directed Sum Cut. Un grand nombre de ces problèmes sont NP-complets.

Soit \(G=(V,A)\) un graphe orienté sans circuit. On lui associe son graphe de co-comparabilité \(H_G=(V,E)\), obtenu en ajoutant une arête entre deux sommets \(i\) et \(j\) de \(G\) lorsqu’il n’existe aucun chemin reliant \(i\) à \(j\) ni aucun chemin reliant \(j\) à $i)dans $G\). Nous nous intéressons à la dégénérescence \(d\) de ce graphe, soit le plus petit entier \(d\) tel que tout sous-graphe non vide possède au moins un sommet de degré au plus \(d\).

Une coupe de \(G\) consiste à partitionner les sommets en deux sous-ensembles \(S_1\) et \(S_2\) de telle sorte qu’il n’existe aucun arc allant de \(S_2\) vers \(S_1\). On montre qu’il existe une bijection entre les coupes de \(G\) et les cliques de \(H_G\). De plus, si \(H_G\) est de dégénérescence \(d\), son nombre de cliques est borné par \(n2^d\), où \(n=|V|\). On peut alors énumérer l’ensemble des coupes de \(G\) en temps \(\mathcal{O}(d2^d n^2)\).

Cette propriété permet de concevoir, pour les différents problèmes d’optimisation considérés, des algorithmes de programmation dynamique dont la complexité est de la forme \(\mathcal{O}\bigl(f(d)n^{\mathcal{O}(1)}\bigr)\). Nous discuterons dans un deuxième temps de l’implémentation de cette méthode pour plusieurs problèmes, ainsi que de sa comparaison expérimentale avec d’autres approches de la littérature.