Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00412
Symmetry Breaking Constraints for the Minimum Deficiency Problem
Sivan Altinakar,
Gilles Caporossi, and
Alain Hertz
Vol. 21, no. 2, pp. 195218, 2017. Regular paper.
Abstract An edgecoloring 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 edgecoloring 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 edgecoloring.
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 LexLeader 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 speedup of the constraint programming model.

Submitted: August 2016.
Reviewed: December 2016.
Revised: January 2017.
Accepted: January 2017.
Final: January 2017.
Published: January 2017.
Communicated by
Giuseppe Liotta

Journal Supporters
