2026-08-07T07:37:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16678 2024-03-06T10:58:02Z ddc:004 open_access

A SAT Attack on Rota’s Basis Conjecture Kirchweger, Markus Scheucher, Manfred Szeider, Stefan SAT modulo Symmetry (SMS) dynamic symmetry breaking Rota’s basis conjecture matroid 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Markus Kirchweger and Manfred Scheucher and Stefan Szeider 2022 Is Part Of LIPIcs, Volume 236, 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAT.2022.4 urn:nbn:de:0030-drops-166780 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2022.4 eng https://creativecommons.org/licenses/by/4.0/legalcode