Breaking symmetries in graphs: the nauty way

Michael Codish, Graeme Gange, Avraham Itzhakov, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

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 languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication22nd International Conference, CP 2016 Toulouse, France, September 5–9, 2016 Proceedings
EditorsMichel Rueher
Place of PublicationCham Switzerland
PublisherSpringer
Pages157-172
Number of pages16
ISBN (Electronic)9783319449531
ISBN (Print)9783319449524
DOIs
Publication statusPublished - 2016
Externally publishedYes
EventInternational Conference on Principles and Practice of Constraint Programming 2016 - Toulouse, France
Duration: 5 Sep 20169 Sep 2016
Conference number: 22d
http://cp2016.a4cp.org/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9892
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2016
Abbreviated titleCP 2016
CountryFrance
CityToulouse
Period5/09/169/09/16
Internet address

Cite this

Codish, M., Gange, G., Itzhakov, A., & Stuckey, P. J. (2016). Breaking symmetries in graphs: the nauty way. In M. Rueher (Ed.), 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