"Detecting Symmetries by Branch & Cut (Journal Version)"
Article by Christoph Buchheim, Michael Jünger, available as BibTeX Source.
Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger
Preprint Key:	zaik2002-438
Keywords:	branch-and-cut, integer programming, symmetry
MSC codes:	20B25, 90C10, 90C35
This article was published in 2003 by Springer in the journal "Mathematical Programming B" (edited by E. Cornejols), volume 98, pages 369-384. (Special Issue in Honor of Egon Balas)
Abstract:	The NP-hard problem of finding symmetries in an abstract graph plays an important role in automatic graph drawing and other applications. In this paper, we present an exact algorithm for automorphism and symmetry detection based on the branch & cut technique. We introduce IP-models for these problems and investigate the structure of the corresponding polytopes. For automorphisms, a complete description of the polytope is derived from a given set of generators of the automorphism group. The rotation polytopes are shown to be related to the asymmetric traveling salesman polytope, while the reflection polytope is related to the matching polytope. The algorithm was implemented within the ABACUS-framework and proves to run fast in practice.