论文标题
从基于宽度的模型检查到基于宽度的自动定理证明
From Width-Based Model Checking to Width-Based Automated Theorem Proving
论文作者
论文摘要
在参数化复杂性理论的领域中，图宽度测量的研究与基于宽度的模型检查算法的开发密切相关。在这项工作中，我们引入了一个通用框架，以将一类的基于宽度的模型检查算法转换为算法，该算法可用于测试图形理论猜想的有效性，这些构想构想在有界宽度的图形类别上。我们的框架是模块化的，可以针对图形的几个宽度宽度测量，包括树宽和cliquewidth。 作为我们框架的定量应用，我们从分析上证明，对于几种长期以来的图理论猜想，存在一种算法，该算法将数字$ k $作为输入作为输入，并在$ k^{o（o（1）}中正确确定double Expartential in $ k^{o（1）} $是否有效，在所有的treewidth of toodwidth of teewidth of teepthth of teemwidth yoss $ k $ a $ k $ a的所有图表都有效。这些上限最多可被视为上限的上限，这些界限最多可在$ k $的treewidth级别上的这些猜想的构想/调谐方案，在使用先前可用的技术获得的理论上界面上有了显着改善。
In the field of parameterized complexity theory, the study of graph width measures has been intimately connected with the development of width-based model checking algorithms for combinatorial properties on graphs. In this work, we introduce a general framework to convert a large class of width-based model-checking algorithms into algorithms that can be used to test the validity of graph-theoretic conjectures on classes of graphs of bounded width. Our framework is modular and can be applied with respect to several well-studied width measures for graphs, including treewidth and cliquewidth. As a quantitative application of our framework, we prove analytically that for several long-standing graph-theoretic conjectures, there exists an algorithm that takes a number $k$ as input and correctly determines in time double-exponential in $k^{O(1)}$ whether the conjecture is valid on all graphs of treewidth at most $k$. These upper bounds, which may be regarded as upper-bounds on the size of proofs/disproofs for these conjectures on the class of graphs of treewidth at most $k$, improve significantly on theoretical upper bounds obtained using previously available techniques.
