通过使用灭灭灵灵灭灵灵,提出循环性和可达性编码 (Propositional Encodings of Acyclicity and Reachability by using Vertex Elimination)

We introduce novel methods for encoding acyclicity and s-t-reachability constraints for propositional formulas with underlying directed graphs. They are based on vertex elimination graphs, which makes them suitable for cases where the underlying graph is sparse. In contrast to solvers with ad hoc constraint propagators for acyclicity and reachability constraints such as GraphSAT, our methods encode these constraints as standard propositional clauses, making them directly applicable with any SAT solver. An empirical study demonstrates that our methods together with an efficient SAT solver can outperform both earlier encodings of these constraints as well as GraphSAT, particularly when underlying graphs are sparse.

翻译：我们引入了新颖的方法,用于对带有基本定向图表的标语公式进行编码循环性和可达性限制,这些公式以顶顶点消除图为基础,因此适合基本图表稀少的情况。与诸如GigapSAT等具有周期性和可及性限制的特设限制宣传器的解决问题者相比,我们的方法将这些限制作为标准标语条款,使这些限制与任何SAT求解器直接适用。一项实证研究表明,我们的方法与高效的SAT求解器一道,可以超越这些限制的早期编码以及GigapSAT,特别是在基本图表稀少的情况下。