Szeider, S. (2025, August 2). SAT Modulo Symmetries: A Survey [Presentation]. the 10th International Workshop on Satisfiability Checking and Symbolic Computation (SC-Square 2025), Stuttgart, Germany. http://hdl.handle.net/20.500.12708/225759
E192-01 - Forschungsbereich Algorithms and Complexity E056-13 - Fachbereich LogiCS E056-23 - Fachbereich Innovative Combinations and Applications of AI and ML (iCAIML)
-
Date (published):
2-Aug-2025
-
Event name:
the 10th International Workshop on Satisfiability Checking and Symbolic Computation (SC-Square 2025)
en
Event date:
2-Aug-2025
-
Event place:
Stuttgart, Germany
-
Keywords:
SAT modulo Symmetries; graphs; NP problems
en
Abstract:
SAT modulo Symmetries (SMS) is a framework for exhaustive isomorph-free generation of combinatorial objects with prescribed properties. The framework tightly integrates a CDCL SAT solver with a custom dynamic symmetry-breaking algorithm through the IPASIR-Up interface. During solving, partially defined graphs are tested for extendability to canonical fully defined graphs; when extension is impossible, a blocking clause is learned. The framework handles co-NP problems such as non-k-colorability and planarity through additional propagators. SMS generates DRAT proofs, providing an additional layer of confidence in the results. This talk will present the theoretical foundations of SMS, examine applications to extremal combinatorics, and demonstrate the system in action.