Complexité et cassage de symétrie pour le problème de la déficience d'un graphe

Une coloration d'arête d'un graphe G=(V,E) est une fonction c qui assigne un entier c(e) (appelé une couleur) dans {0, 1, 2,...} à chaque arête e dans E de sorte que des couleurs différentes soient assignées à des arêtes adjacentes. Une coloration d'arête est compacte si les couleurs des arêtes incidentes à chaque sommet forment un ensemble d'entiers consécutifs. Le problème appelé déficience consiste à déterminer le nombre minimum d'arêtes pendantes à rajouter au graphe pour que le graphe résultant ait une coloration d'arête compacte. Parmi les variations de ce problème, on compte le problème de la coloration d'arête compacte linéaire (k−LCCP) où il est possible d'utiliser uniquement les k couleurs dans {0, 1, ... , k−1}, et le problème de la coloration d'arête compacte cyclique (k−CCCP) où additionnellement la couleur 0 est considérée consécutive à la couleur k−1. Nous proposons une réduction polynomiale du k−LCCP (optionnellement avec des couleurs imposées ou interdites sur certaines arêtes) au k−CCCP lorsque k≥12, et au 12-CCCP lorsque k<12. Nous proposons et comparons également la performance de 3 modélisations en Programmation en Nombres Entiers et un modèle en Programmation par Contraintes pour le problème de la déficience, et déterminons le dernier comme étant le plus approprié pour ce problème. En raison des symétries, une instance du problème de déficience peut avoir de nombreuses solutions optimales équivalentes. Nous présentons une approche pour générer un petit ensemble de contraintes, appelées GAMBLLE, destinée à casser la symétrie, qui peuvent être incorporées au modèle en programmation par contrainte. Les contraintes GAMBLLE sont inspirées des contraintes de Lex-Leader, basées sur les automorphismes de graphe, et agissent sur des familles de variables permutables. Nous analysons leur impact sur la réduction du nombre de solutions optimales, ainsi que le gain de temps obtenu lors de la résolution d'une modélisation en programmation par contrainte.