---
title: "Breaking Symmetries in Graph Representation"
authors:
  - "Michael Codish"
  - "Alice Miller"
  - "Patrick Prosser"
  - "Peter J. Stuckey"
doi: ""
url: "https://ijcai.org/proceedings/2013/83"
pdf: "https://ijcai.org/proceedings/2013/0083.pdf"
venue: "Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence"
year: 2013
pages: "510-515"
track: ""
keywords:
---

# Breaking Symmetries in Graph Representation

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

*Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence*, pages 510-515.

## Abstract

There are many complex combinatorial problems which involve searching for an undirected graph satisfying a certain property. These problems are often highly challenging because of the large number of isomorphic representations of a possible solution. 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.