Breaking symmetries in graph search with canonizing sets

DOI10.1007/S10601-016-9244-ZMaRDI QIDQ2398437zbMATH OpenOpenAlexFDO

Authors Avraham Itzhakov, Michael Codish

Publication date 16 August 2017

Published in Constraints (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1511.08205

zbMATH Keywords

graph search problemsSAT solvingsymmetry breaking

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: There are many complex combinatorial problems which involve searching for an undirected graph satisfying given constraints. Such problems are often highly challenging because of the large number of isomorphic representations of their solutions. This paper introduces effective and compact, complete symmetry breaking constraints for small graph search. Enumerating with these symmetry breaks generates all and only non-isomorphic solutions. For small search problems, with up to $10$ vertices, we compute instance independent symmetry breaking constraints. For small search problems with a larger number of vertices we demonstrate the computation of instance dependent constraints which are complete. We illustrate the application of complete symmetry breaking constraints to extend two known sequences from the OEIS related to graph enumeration. We also demonstrate the application of a generalization of our approach to fully-interchangeable matrix search problems.

Recommendations

• Constraints for symmetry breaking in graph representation
• Generating effective symmetry-breaking predicates for search problems
• Breaking symmetries with lex implications
• Optimal symmetry breaking for graph problems
• Symmetry breaking revisited

Cites work

• R(4, 5) = 25
• Boolean equi-propagation for concise and efficient SAT encodings of combinatorial problems
• Breaking instance-independent symmetries in exact graph coloring
• Cataloguing the graphs on 10 vertices
• Conflict Anticipation in the Search for Graph Automorphisms
• Constraints for symmetry breaking in graph representation
• Degree sequences of highly irregular graphs
• Every one a Winner or how to Avoid Isomorphism Search when Cataloguing Combinatorial Configurations
• Fast generation of cubic graphs
• General Symmetry Breaking Constraints
• Generating effective symmetry-breaking predicates for search problems
• Highly irregular graphs
• scientific article; zbMATH DE number 3737696 (Why is no real title available?)
• scientific article; zbMATH DE number 3639629 (Why is no real title available?)
• scientific article; zbMATH DE number 1903357 (Why is no real title available?)
• Isomorph-Free Exhaustive Generation
• Principles and Practice of Constraint Programming – CP 2003
• Small Ramsey numbers
• Symmetry and Satisfiability: An Update
• The complexity of symmetry-breaking formulas

Cited in

(8)

• Optimal symmetry breaking for graph problems
• Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs
• Constraints for symmetry breaking in graph representation
• Generating effective symmetry-breaking predicates for search problems
• Evolutionary Computation in Combinatorial Optimization
• An adaptive prefix-assignment technique for symmetry reduction
• SAT modulo symmetries for graph generation and enumeration
• Breaking symmetries from a set-covering perspective

Describes a project that uses

Uses Software

• Glucose
• Easychair
• Saucy
• OEIS
• nauty

This page was built for publication: Breaking symmetries in graph search with canonizing sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2398437)