Research map / Graph learning / Graph algorithms and clustering
Incremental Symmetry Breaking Constraints for Graph Search Problems
Avraham Itzhakov, Michael Codish
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| compute symmetry breaking constraints incrementally instead of directly | column-wise symmetry breaking · order 11 graphs | computation time: 12.39d -> 5.56d | Improved |
| incremental instead of direct computation | column-wise symmetry breaking · order 10 graphs | computation time: 3.73h -> 2.10h | Improved |
| incremental instead of direct computation | column-wise symmetry breaking · order 5 graphs | computation time: 0.07s -> 0.08s | No clear effect |
| incremental instead of direct computation | column-wise symmetry breaking · order 3-11 | constraint size: 289,698 -> 290,117 | No clear effect |
| use compact column-wise constraints instead of LexLeader | symmetry breaking · order 11 | constraint size: 2,195,424,000 -> 289,698 | Improved |
| use specialized constraints per order-7 canonical graph instead of simplified general ones | symmetry breaking · order 11 | average constraint size: 58,561.44 -> 873.03 | Improved |
| generate and extend instead of generate and test | word-representable graph enumeration · order 11 | computation time: 1,100d -> 4.04d | Improved |
| generate and extend instead of generate and test | word-representable graph enumeration · order 10 | computation time: 74h -> 1.41h | Improved |
| generate and extend instead of direct constraint solving | totally magic graphs · order >= 9 | solutions found | Improved |
| generate and extend for totally magic graphs vs Jager and Arnold | totally magic graph enumeration · order 11 | total computation days: 13,595 -> 976.36 | Improved |
| generate and extend for totally magic graphs vs Jager and Arnold | totally magic graph enumeration · order 10 | total computation days: 21.70 -> 7.21 | Improved |
| filter with step 1 before testing totally magic property | totally magic graph enumeration · order 11 | graphs tested: 1,018,997,864 -> 91,397,498 | Improved |
Closest papers by meaning
- Breaking More Composition Symmetries Using Search Heuristics (AAAI 2016 · similarity 0.87)
- Exploiting Symmetries in MUS Computation (AAAI 2025 · similarity 0.86)
- Breaking Symmetries in Quantified Graph Search: A Comparative Study (AAAI 2025 · similarity 0.86)
- SAT-Based Algorithms for Regular Graph Pattern Matching (AAAI 2024 · similarity 0.85)
- Incremental Topological Ordering and Cycle Detection with Predictions (ICML 2024 · similarity 0.85)
- Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
