<div class="csl-bib-body">
<div class="csl-entry">Kirchweger, M., Scheucher, M., & Szeider, S. (2022). A SAT Attack on Rota’s Basis Conjecture. In <i>25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)</i> (pp. 1–18). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.SAT.2022.4</div>
</div>
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/150220
-
dc.description.abstract
The SAT modulo Symmetries (SMS) is a recently introduced framework for dynamic symmetry breaking in SAT instances. It combines a CDCL SAT solver with an external lexicographic minimality checking algorithm. We extend SMS from graphs to matroids and use it to progress on Rota’s Basis Conjecture (1989), which states that one can always decompose a collection of r disjoint bases of a rank r matroid into r disjoint rainbow bases. Through SMS, we establish that the conjecture holds for all matroids of rank 4 and certain special cases of matroids of rank 5. Furthermore, we extend SMS with the facility to produce DRAT proofs. External tools can then be used to verify the validity of additional axioms produced by the lexicographic minimality check. As a byproduct, we have utilized our framework to enumerate matroids modulo isomorphism and to support the investigation of various other problems on matroids.
en
dc.description.sponsorship
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.relation.ispartofseries
Leibniz International Proceedings in Informatics (LIPIcs)
-
dc.rights.uri
http://creativecommons.org/licenses/by/4.0/
-
dc.subject
dynamic symmetry breaking
en
dc.subject
matroid
en
dc.subject
Rota’s basis conjecture
en
dc.subject
SAT modulo Symmetry (SMS)
en
dc.title
A SAT Attack on Rota’s Basis Conjecture
en
dc.type
Inproceedings
en
dc.type
Konferenzbeitrag
de
dc.rights.license
Creative Commons Namensnennung 4.0 International
de
dc.rights.license
Creative Commons Attribution 4.0 International
en
dc.relation.publication
25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)