TY - JOUR
AU - Itzhakov, Avraham
AU - Codish, Michael
PY - 2020/04/03
Y2 - 2021/04/11
TI - Incremental Symmetry Breaking Constraints for Graph Search Problems
JF - Proceedings of the AAAI Conference on Artificial Intelligence
JA - AAAI
VL - 34
IS - 02
SE - AAAI Technical Track: Constraint Satisfaction and Optimization
DO - 10.1609/aaai.v34i02.5513
UR - https://ojs.aaai.org/index.php/AAAI/article/view/5513
SP - 1536-1543
AB - <p> 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 <em>n</em> graphs can be extended to one for order <em>n</em> + 1 graphs. Moreover, these constraints induce a special property on their canonical solutions: An order <em>n</em> canonical graph contains a canonical subgraph on the first <em>k</em> vertices for every 1 ≤ <em>k</em> ≤ <em>n</em>. This facilitates a “generate and extend” paradigm for parallel graph search problem solving: To solve a graph search problem φ on order <em>n</em> graphs, first generate the canonical graphs of some order <em>k</em> < <em>n</em>. Then, compute canonical solutions for φ by extending, in parallel, each canonical order <em>k</em> graph together with suitable symmetry breaking constraints. The contribution is that the proposed symmetry breaking constraints enable us to extend the order <em>k</em> canonical graphs to order <em>n</em> canonical solutions. We demonstrate our approach through its application on two hard graph search problems.</p>
ER -