### Abstract

Symmetry breaking is an essential component when solving graph search problems as it restricts the search space to that of canonical representations. There are an abundance of powerful tools, such as nauty, which apply to find the canonical representation of a given graph and to test for isomorphisms given a set of graphs. In contrast, for graph search problems, current symmetry breaking techniques are partial and solvers unnecessarily explore an abundance of isomorphic parts of the search space. This paper is novel in that it introduces complete symmetry breaking for graph search problems by modeling, in terms of constraints, the same ideas underlying the algorithm applied in tools like nauty. Whereas nauty tests given graphs, symmetry breaks restrict the search space and apply during generation.

Original language | English |
---|---|

Title of host publication | Principles and Practice of Constraint Programming |

Subtitle of host publication | 22nd International Conference, CP 2016 Toulouse, France, September 5–9, 2016 Proceedings |

Editors | Michel Rueher |

Place of Publication | Cham Switzerland |

Publisher | Springer |

Pages | 157-172 |

Number of pages | 16 |

ISBN (Electronic) | 9783319449531 |

ISBN (Print) | 9783319449524 |

DOIs | |

Publication status | Published - 2016 |

Externally published | Yes |

Event | International Conference on Principles and Practice of Constraint Programming 2016 - Toulouse, France Duration: 5 Sep 2016 → 9 Sep 2016 Conference number: 22d http://cp2016.a4cp.org/ |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 9892 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | International Conference on Principles and Practice of Constraint Programming 2016 |
---|---|

Abbreviated title | CP 2016 |

Country | France |

City | Toulouse |

Period | 5/09/16 → 9/09/16 |

Internet address |

## Cite this

*Principles and Practice of Constraint Programming: 22nd International Conference, CP 2016 Toulouse, France, September 5–9, 2016 Proceedings*(pp. 157-172). (Lecture Notes in Computer Science ; Vol. 9892 ). Springer. https://doi.org/10.1007/978-3-319-44953-1_11