Symmetry-Breaking Constraints for Directed Graphs

Abstract

Finding a graph with given properties occurs as a sub-problem of many important problems in A.I. and other areas of computer science. Main approaches to solving such problems include automated reasoning and constraint satisfaction methods. These can often be substantially sped up by considering only a subset of graphs for each equivalence class of isomorphic graphs, motivating the use of symmetry-breaking constraints for graphs. We present a symmetry-breaking constraint for directed graphs, generalizing earlier works that have presented such constraints for undirected graphs without loops, and experimentally demonstrate their effectiveness.