[Zurück]

B. Klocker, H. Fleischner, G. Raidl:
"A SAT Approach for Finding Sup-Transition-Minors";
Vortrag: Learning and Intelligent OptimizatioN Conference LION, Chania, Crete, Greece; 27.05.2019 - 31.05.2019; in: "Learning and Intelligent Optimization", LNCS, 11968 (2019), ISBN: 978-3-030-38628-3; S. 325 - 341.

The cycle double cover conjecture is a famous longstanding unsolved
conjecture in graph theory. It is related and can be reduced to the compatible
circuit decomposition problem. Recently Fleischner et al. (2018) provided a sufficient
condition for a compatible circuit decomposition, which is called SUD-
K5-minor freeness. In a previous work we developed an abstract mathematical
model for finding SUD-K5-minors and based on the model a mixed integer linear
program (MIP). In this work we propose a respective boolean satisfiability (SAT)
model and compare it with the MIP model in computational tests. Non-trivial
symmetry breaking constraints are proposed, which improve the solving times of
both models considerably. Compared to the MIP model the SAT approach performs
significantly better. We use the faster algorithm to further test graphs of
graph theoretic interest and were able to get new insights. Among other results
we found snarks with 30 and 32 vertices that do not contain a perfect pseudomatching,
that is a spanning subgraph consisting of K2 and K1;3 components,
whose contraction leads to a SUD-K5-minor free graph.

http://dx.doi.org/10.1007/978-3-030-38629-0_27

https://publik.tuwien.ac.at/files/publik_284801.pdf