2 papers
cs.CC2024
Finding hardness reductions automatically using SAT solvers
Helena Bergold, Manfred Scheucher, Felix Schröder
In this article, we show that the completion problem, i.e. the decision problem whether a partial structure can be completed to a full structure, is NP-complete for many combinator…
cs.CG2023
Using SAT to study plane Hamiltonian substructures in simple drawings
Helena Bergold, Stefan Felsner, Meghana M. Reddy +1
In 1988 Rafla conjectured that every simple drawing of a complete graph contains a plane, i.e., non-crossing, Hamiltonian cycle. The conjecture is far from being resolved. Th…