Symmetry Breaking Constraints for the Minimum Deficiency Problem

Abstract

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,\dotsc\}$ to every edge $e\in E$ so that adjacent edges receive different colors. An edge-coloring is compact if the colors of the edges incident to every vertex form a set of consecutive integers. The minimum 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. Because of symmetries, an instance of the minimum deficiency problem can have many equivalent optimal solutions. We present a way to generate a set of symmetry breaking constraints, called ${\rm {\small GAMBLLE}}$ constraints, that can be added to a constraint programming model. The ${\rm {\small 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.