Compact constraints improve graph search efficiency without huge size increase
Compact Partial Symmetry Breaking for Graph Search Problems
Logic in Computer Science
Summary
Graph search problems become very slow when many symmetrical solutions exist, and fully removing these symmetries is often too large to handle. The authors introduced a method that picks important patterns to break symmetries partially but effectively, keeping the problem size small. Their approach finds a good balance between cutting down redundant solutions and keeping the constraints manageable. Tests showed their method works better than previous partial symmetry breaking techniques on graphs up to 25 nodes.
What this means in practice
- •For software engineers working on graph algorithms: Implement compact symmetry breaking constraints to speed up graph search problems by reducing redundant searches efficiently.
- •For developers of constraint and sat solvers: Integrate pattern-based partial symmetry breaking clauses to improve solver performance on graph search benchmarks with moderate graph sizes.
Authors
Michael Codish, Mikoláš Janota, Peter J. Stuckey
Abstract
Symmetry breaking in graph search problems remains challenging: complete symmetry breaking constraints are typically exponential in size, while partial approaches trade precision for scalability. We introduce a strength-driven, redundancy-aware methodology for constructing compact partial symmetry breaking constraints based on graph patterns. Each pattern corresponds to a Boolean clause over equality literals and can be integrated directly into CP or SAT models. Our approach incrementally selects strong, non-redundant graph patterns, yielding partial symmetry breaks that achieve substantial pruning of non-canonical graphs while remaining compact in size. This provides a principled framework for deriving lightweight partial symmetry breaking constraints which are significantly more precise than all published state-of-the-art alternatives. We evaluate the proposed constraints on graph instances with up to 25 vertices using a redundancy ratio metric. The resulting partial symmetry breaks constitute only a small fraction of the size of complete symmetry breaking constraints, while delivering significant performance improvements across several graph search benchmarks compared to previously defined partial symmetry breaking methods.