Hypergraph Acyclicities and Propositional Model Counting

We present in this talk structural restrictions of CNF-formulas to find tractable classes for the problem #SAT. We explain why α -acyclicity is not appropriate for this problem. We then introduce β -acyclicity and present a polynomial time algorithm for #SAT on β -acyclic CNF-formulas.

Authors

• Florent Capelli

Keywords

No keywords are indexed for this paper.