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

An edge-coloring of a graph G=(V,E) is a function c that assigns an integer c(e) (called color) in {0, 1, 2,...} to every edge e in E so that adjacent edges are assigned different colors. An edge-coloring is compact if the colors of the edges incident to every vertex form a set of consecutive integers. The deficiency problem is to determine the minimum number of pendant edges that must be added to a graph such that the resulting graph admits a compact edge-coloring. Variations of this problem include the linear compact k-edge-coloring problem (k−LCCP) where there are only the k colors of {0, 1, ... , k−1} available, and the cyclic compact k-edge-coloring problem (k−CCCP) where additionally color 0 is considered consecutive to color k−1. We demonstrate a polynomial reduction of the k−LCCP (with optionally additional imposed or forbidden colors on some edges) to the k−CCCP when k≥12, and to the 12−CCCP when k<12. We also propose and compare the performance of three integer programming models and one constraint programming model for the deficiency problem, and determine the latter to be the best suited to model this problem. Because of symmetries, an instance of the deficiency problem can have many equivalent optimal solutions. We present a way to generate a small set of symmetry breaking constraints, called GAMBLLE constraints, that can be added to a constraint programming model. The GAMBLLE constraints are inspired by the Lex-Leader ones, based on automorphisms of graphs, and act on families of permutable variables. We analyze their impact on the reduction of the number of optimal solutions as well as on the speed-up of the constraint programming model.

Résumé

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.