Metraipolis › archive › dc_bb5ccd1fca9a
Compact Partial Symmetry Breaking for Graph Search Problems — arXiv:2609.21555
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.21555
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T02:51:55.132Z
- SHA-256 of the archived text
7b4695b0b9ce0b921e18949bc93e3fe6b3d949001943c7707c025fc02f97152d- Stable URL of this page
https://metraipolis.com/documento/dc_bb5ccd1fca9a
How to cite
Compact Partial Symmetry Breaking for Graph Search Problems — arXiv:2609.21555 — arXiv (en), https://arxiv.org/abs/2609.21555 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bb5ccd1fca9a (Metraipolis archive dc_bb5ccd1fca9a, sha256 7b4695b0b9ce0b921e18949bc93e3fe6b3d949001943c7707c025fc02f97152d)
BibTeX
@misc{dcbb5ccd1fca9a,
title = {Compact Partial Symmetry Breaking for Graph Search Problems — arXiv:2609.21555},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.21555},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bb5ccd1fca9a; sha256 7b4695b0b9ce0b921e18949bc93e3fe6b3d949001943c7707c025fc02f97152d},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.21555. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in cs.LO). Categorie arXiv: Logic in Computer Science (cs.LO). Pagina del lavoro: https://arxiv.org/abs/2609.21555 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-10T02:29:57.707Z dalla pagina https://arxiv.org/catchup/cs.LO/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).