2026· International Conference on Theory and Applications of Satisfiability Testing· pp. 4:1-4:19· 1 citation· 34 references
Computer Science
TL;DR
This paper presents a new algorithm that treats symmetry breaking not merely as a restriction mechanism, but as a simplification mechanism, which enables strong formula simplifications and substantially outperforms lex-leader and orbitopal fixing while producing compact proofs.
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...
Michael Codish, Mikoláš Janota, Peter James Stuckey· 0 citations
A cardinality-aware local search framework to solve SAT with cardinality constraints, denoted as CardSAT-LS, which integrates a preprocessing phase based on the generalized unit propagation and resolution, a cardinality-sensitive scoring function combining the make-break mechanism and cardinality violation, and an init...
Shu-Li Hu, Dian Ling, Jia-Qi Li et al.· Proceedings of the Thirty-Fi...· 0 citations
String operations are integral to program analysis, yet reasoning about the ubiquitous split operation remains a challenge. SMT solvers have difficulty with split because it transforms a string into a variable-length sequence, creating a structural mismatch that leads to uninterpreted abstractions or unsound bounded ap...
Rui Han, Zi-Heng Wang, Bao-Quan Cui et al.· 0 citations
In The Art of Computer Programming, Knuth benchmarked 10 encoding techniques for computing the chromatic number of the queen's graph: the minimum number of colors needed to color the squares of an $n \times n$ chessboard so that no two squares sharing a row, column, or diagonal receive the same color. In this paper, we...
Bernardo Subercaseaux, Benjamin Przybocki, Marijn J. H. Heule· 0 citations
A theoretical analysis of the conditions under which LBBD, including cuts, can preserve optimality in the context of Answer Set Programming (ASP), a prominent logic-based language in the field of Artificial Intelligence and introduces a general-purpose algorithm that preserves the optimality guarantees of Bender Decomp...
Carmine Dodaro, Antonio Ielo, M. Maratea et al.· Proceedings of the Thirty-Fi...· 0 citations
The development of round elimination into a general-purpose technique [PODC 2019] marked a turning point in our understanding of the hardness of many graph problems in the distributed setting and led to several breakthrough results. However, the round elimination technique seems unable to yield randomized lower bounds...
A. Balliu, Francesco d'Amore, D. Olivetti· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
