Investigation of the Efficiency of Conversion of Directed Graphs to 3-SAT Problems
Gábor Kusper, Csaba Bíró, Tamás Balla · 2020
In our previous works we introduced several 2-SAT (Strong Model) and 3-SAT (Weak Model, Balatonboglár Model and Simplified Balatonboglár Model) models of directed graphs. We showed that Balatonboglár Model is a Black-and-White 3-SAT problem if and only if the represented directed graph is strongly connected. Balatonboglár Model generates a lot of so called Negative-Negative-Positive shaped clauses to represent cycles of the directed graph without detecting cycles, i.e., it can be generated fast but it is bigger than necessary. To overcome this problem, we have introduced the Simplified Balatonboglár Model. In this article, first, we give an example to illustrate the various conversion methods (models) and we briefly explain the theoretical background. After, we present the results of the latest version of CSFLOC on benchmarks generated by different conversion models. Finally, we show how the file sizes of benchmarks and the number of unused clauses changes as a function of the density of the represented directed graph.