Constraints for symmetry breaking in graph representation

Michael Codish, Alice Miller, Patrick Prosser, Peter J. Stuckey

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Many complex combinatorial problems arising from a range of scientific applications (such as computer networks, mathematical chemistry and bioinformatics) involve searching for an undirected graph satisfying a given property. Since for any possible solution there can be a large number of isomorphic representations, these problems can quickly become intractable. One way to mitigate this problem is to eliminate as many isomorphic copies as possible by breaking symmetry during search - i.e. by introducing constraints that ensure that at least one representative graph is generated for each equivalence class, but not the entire class. The goal is to generate as few members of each class as possible - ideally exactly one: the symmetry break is said to be complete in this case. In this paper we introduce novel, effective and compact, symmetry breaking constraints for undirected graph search. While incomplete, these prove highly beneficial in pruning the search for a graph. We illustrate the application of symmetry breaking in graph representation to resolve several open instances in extremal graph theory. We also illustrate the application of our approach to graph edge coloring problems which exhibit additional symmetries due to the fact that the colors of the edges in any solution can be permuted.

Original languageEnglish
Pages (from-to)1-24
Number of pages24
JournalConstraints
Volume24
Issue number1
DOIs
Publication statusPublished - 2018
Externally publishedYes

Keywords

  • Constraints and satisfiability
  • Graph theory
  • Symmetry and search

Cite this