论文标题
加权模型以双宽度计数
Weighted Model Counting with Twin-Width
论文作者
论文摘要
Bonnet等。 （FOCS 2020）引入了图形不变的双宽度，并表明许多NP硬化问题对于有界双宽度的图形是可以处理的，从而概括了其他宽度测量的相似结果，包括树宽度和clique宽度。在本文中，我们研究了双宽度用于解决命题满足问题（SAT）和命题模型计数的使用。我们特别专注于有限的加权模型计数（BWMC），该模型计数（BWMC）将CNF公式$ f $以及绑定的$ k $以及最多具有$ k $正面文字的所有加权总和。 BWMC不仅概括了SAT，还概括了（加权）模型计数。 我们开发了CNF公式的“签名”双宽度的概念，并确定当由认证的签名的$ f $ plus $ k $参数化时，BWMC是固定参数可进行的。我们表明，这个结果很紧：如果一个人希望保留固定参数的障碍性，即使出于更轻松的问题，也不可以丢弃绑定的$ k $，也不可以使用香草双宽度。我们的理论结果通过经验评估和对各种CNF公式的双宽度的比较进行了补充。
Bonnet et al. (FOCS 2020) introduced the graph invariant twin-width and showed that many NP-hard problems are tractable for graphs of bounded twin-width, generalizing similar results for other width measures, including treewidth and clique-width. In this paper, we investigate the use of twin-width for solving the propositional satisfiability problem (SAT) and propositional model counting. We particularly focus on Bounded-ones Weighted Model Counting (BWMC), which takes as input a CNF formula $F$ along with a bound $k$ and asks for the weighted sum of all models with at most $k$ positive literals. BWMC generalizes not only SAT but also (weighted) model counting. We develop the notion of "signed" twin-width of CNF formulas and establish that BWMC is fixed-parameter tractable when parameterized by the certified signed twin-width of $F$ plus $k$. We show that this result is tight: it is neither possible to drop the bound $k$ nor use the vanilla twin-width instead if one wishes to retain fixed-parameter tractability, even for the easier problem SAT. Our theoretical results are complemented with an empirical evaluation and comparison of signed twin-width on various classes of CNF formulas.
