| GANIAN, Robert and Stefan SZEIDER. New Width Parameters for Model Counting. Online. In Serge Gaspers and Toby Walsh. Theory and Applications of Satisfiability Testing - {SAT} 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings. Nemecko: Springer, 2017, p. 38-52. ISBN 978-3-319-66262-6. Available from: https://dx.doi.org/10.1007/978-3-319-66263-3_3. |
Other formats:
BibTeX
LaTeX
RIS
@inproceedings{1414045,
author = {Ganian, Robert and Szeider, Stefan},
address = {Nemecko},
booktitle = {Theory and Applications of Satisfiability Testing - {SAT} 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings},
doi = {http://dx.doi.org/10.1007/978-3-319-66263-3_3},
editor = {Serge Gaspers and Toby Walsh},
keywords = {Treewidth; Model Counting; SAT; Parameterized Complexity},
howpublished = {elektronická verze "online"},
language = {eng},
location = {Nemecko},
isbn = {978-3-319-66262-6},
pages = {38-52},
publisher = {Springer},
title = {New Width Parameters for Model Counting},
url = {https://link.springer.com/chapter/10.1007/978-3-319-66263-3_3#citeas},
year = {2017}
}
TY - JOUR
ID - 1414045
AU - Ganian, Robert - Szeider, Stefan
PY - 2017
TI - New Width Parameters for Model Counting
PB - Springer
CY - Nemecko
SN - 9783319662626
KW - Treewidth
KW - Model Counting
KW - SAT
KW - Parameterized Complexity
UR - https://link.springer.com/chapter/10.1007/978-3-319-66263-3_3#citeas
L2 - https://link.springer.com/chapter/10.1007/978-3-319-66263-3_3#citeas
N2 - 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.
ER -
GANIAN, Robert and Stefan SZEIDER. New Width Parameters for Model Counting. Online. In Serge Gaspers and Toby Walsh. \textit{Theory and Applications of Satisfiability Testing - $\{$SAT$\}$ 2017 - 20th International Conference, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings}. Nemecko: Springer, 2017, p.~38-52. ISBN~978-3-319-66262-6. Available from: https://dx.doi.org/10.1007/978-3-319-66263-3\_{}3.
|
