New Width Parameters for Model Counting

被引:8
作者
Ganian, Robert [1 ,2 ]
Szeider, Stefan [1 ]
机构
[1] TU Wien, Algorithms & Complex Grp, Vienna, Austria
[2] FI MU, Brno, Czech Republic
来源
THEORY AND APPLICATIONS OF SATISFIABILITY TESTING (SAT 2017) | 2017年 / 10491卷
基金
奥地利科学基金会;
关键词
SOLVING NUMBER-SAT; ALGORITHMS; SATISFIABILITY; COMPLEXITY; CONFLICTS;
D O I
10.1007/978-3-319-66263-3_3
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We study the parameterized complexity of the propositional model counting problem #SAT for CNF formulas. As the parameter we consider the treewidth of the following two graphs associated with CNF formulas: the consensus graph and the conflict graph. Both graphs have as vertices the clauses of the formula; in the consensus graph two clauses are adjacent if they do not contain a complementary pair of literals, while in the conflict graph two clauses are adjacent if they do contain a complementary pair of literals. We show that #SAT is fixed-parameter tractable for the treewidth of the consensus graph but W[1]-hard for the treewidth of the conflict graph. We also compare the new parameters with known parameters under which #SAT is fixed-parameter tractable.
引用
收藏
页码:38 / 52
页数:15
相关论文
共 50 条
  • [31] CV-width: A New Complexity Parameter for CNFs
    Oztok, Umut
    Darwiche, Adnan
    21ST EUROPEAN CONFERENCE ON ARTIFICIAL INTELLIGENCE (ECAI 2014), 2014, 263 : 675 - 680
  • [32] Twin-width I: Tractable FO Model Checking
    Bonnet, Edouard
    Kim, Eun Jung
    Thomasse, Stephan
    Watrigant, Remi
    JOURNAL OF THE ACM, 2022, 69 (01)
  • [33] Solving Projected Model Counting by Utilizing Treewidth and its Limits
    Fichte, Johannes K.
    Hecher, Markus
    Morak, Michael
    Thier, Patrick
    Woltran, Stefan
    ARTIFICIAL INTELLIGENCE, 2023, 314
  • [35] Exact Model Counting of Query Expressions: Limitations of Propositional Methods
    Beame, Paul
    Li, Jerry
    Roy, Sudeepa
    Suciu, Dan
    ACM TRANSACTIONS ON DATABASE SYSTEMS, 2017, 42 (01):
  • [36] Approximate Model Counting Via Extension Rule and Clause Reduction
    Liu, Hao
    Ni, Ziao
    Zhou, Wenyang
    Zhang, Tongbo
    Lu, Shuai
    ICIIP'18: PROCEEDINGS OF THE 3RD INTERNATIONAL CONFERENCE ON INTELLIGENT INFORMATION PROCESSING, 2018, : 40 - 45
  • [37] A Scalable Approach to Exact Model and Commonality Counting for Extended Feature Models
    Fernandez-Amoros, David
    Heradio, Ruben
    Cerrada, Jose A.
    Cerrada, Carlos
    IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 2014, 40 (09) : 895 - 910
  • [38] Ising model partition-function computation as a weighted counting problem
    Nagy, Shaan
    Paredes, Roger
    Dudek, Jeffrey M.
    Duenas-Osorio, Leonardo
    Vardi, Moshe Y.
    PHYSICAL REVIEW E, 2024, 109 (05)
  • [39] NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY
    Zhou, Junping
    Su, Weihua
    Wang, Jianan
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2014, 25 (06) : 667 - 678
  • [40] TSK fuzzy model with minimal parameters
    Guenounou, Ouahib
    Dahhou, Boutaib
    Chabour, Ferhat
    APPLIED SOFT COMPUTING, 2015, 30 : 748 - 757