Incremental Symmetry Breaking Constraints for Graph Search Problems

Authors

  • Avraham Itzhakov Ben-Gurion University of the Negev
  • Michael Codish Ben-Gurion University of the Negev

DOI:

https://doi.org/10.1609/aaai.v34i02.5513

Abstract

This paper introduces incremental symmetry breaking constraints for graph search problems which are complete and compact. We show that these constraints can be computed incrementally: A symmetry breaking constraint for order n graphs can be extended to one for order n + 1 graphs. Moreover, these constraints induce a special property on their canonical solutions: An order n canonical graph contains a canonical subgraph on the first k vertices for every 1 ≤ kn. This facilitates a “generate and extend” paradigm for parallel graph search problem solving: To solve a graph search problem φ on order n graphs, first generate the canonical graphs of some order k < n. Then, compute canonical solutions for φ by extending, in parallel, each canonical order k graph together with suitable symmetry breaking constraints. The contribution is that the proposed symmetry breaking constraints enable us to extend the order k canonical graphs to order n canonical solutions. We demonstrate our approach through its application on two hard graph search problems.

Downloads

Published

2020-04-03

How to Cite

Itzhakov, A., & Codish, M. (2020). Incremental Symmetry Breaking Constraints for Graph Search Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02), 1536-1543. https://doi.org/10.1609/aaai.v34i02.5513

Issue

Section

AAAI Technical Track: Constraint Satisfaction and Optimization