Incremental Symmetry Breaking Constraints for Graph Search Problems

Avraham Itzhakov, Michael CodishAAAI 2020 · DOI

Introduction

Graph search problems—finding or counting graphs that satisfy specific combinatorial properties—are fundamental to discrete mathematics and constraint programming. However, these problems are plagued by the "isomorphism explosion." A single graph with $n$ vertices can be represented in $n!$ different ways by permuting vertex labels. Without effective symmetry breaking, solvers waste vast amounts of time exploring redundant, isomorphic regions of the search space.

The Challenge of Symmetry Breaking

To combat redundancy, researchers employ symmetry breaking constraints that force the solver to consider only one "canonical" representative from each isomorphism class. While the "lex-leader" approach (selecting the lexicographically smallest adjacency matrix) is a standard technique, it often produces an exponential number of constraints as $n$ increases, making it computationally intractable for large graphs.

Incremental Column-wise Canonicity

This paper introduces a novel approach based on incremental column-wise canonicity. Unlike traditional row-wise canonical forms, column-wise canonicity possesses a crucial hereditary property: if a graph of order $n$ is canonical, its subgraph formed by the first $k$ vertices is also canonical.

This property enables a "generate and extend" parallel paradigm:

  1. Generate: Enumerate all canonical graphs of a smaller size $k$.
  2. Extend: For each small graph, search for extensions to size $n$ in parallel.

Because the initial $k$ vertices are fixed, the symmetry-breaking constraints for the extension phase can be "specialized," drastically reducing their size and complexity.

Comparison of specialized and simplified constraint sizes across different graph orders.

As shown in the table above, the reduction in constraint size is dramatic. For $n=11$, the average size of specialized constraints is nearly two orders of magnitude smaller than simplified constraints, enabling the solver to process instances that were previously unreachable.

Performance Gains

The authors implemented their method using the BEE constraint compiler and the Glucose 4.0 SAT solver. Their evaluation demonstrates that the incremental algorithm for computing constraints scales significantly better than direct computation.

Performance comparison between direct and incremental constraint computation methods.

The incremental approach achieves a speedup of up to 2.22x for graphs of order 11. More importantly, the "generate and extend" workflow allows for massive parallelism across compute clusters.

Breakthrough Results in Combinatorics

The practical impact of these methods is evidenced by results on two hard problems:

  • Totally Magic Graphs: The authors confirmed the non-existence of solutions for $n=11$ in just 976 CPU days, a 10x improvement over the 13,595 CPU days required by previous state-of-the-art methods.
  • Word-Representable Graphs: The team provided the first-ever enumeration for order $n=12$, identifying over 135 billion non-word-representable connected graphs. They also corrected errors in previously published counts for $n=11$.

Conclusion

By leveraging the hereditary property of column-wise canonicity, this work transforms symmetry breaking from a bottleneck into a parallelizable advantage. The ability to generate specialized, compact constraints opens new doors for exploring the properties of large combinatorial objects that were once considered computationally out of reach.

Summary updated

BibTeX
@inproceedings{itzhakov2020incremental,
  author = {Avraham Itzhakov and Michael Codish},
  title = {{Incremental Symmetry Breaking Constraints for Graph Search Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i02.5513},
}
Figure