Speaker: Johannes K. Fichte (TU Dresden)

Title: Parameterized Algorithmics and Counting: Treewidth in Practice

Abstract: We discuss parameterized algorithms and an application to exact propositional model counting (MC). (W)MC asks for counting the (weighted) number of satisfying assignments of a propositional formula. The problem is known to be beyond NP and a prototypical representative of the class #P.

Various implementations that solve MC employ a SAT-based solving engine. However, we tackle the problem from a theoretical perspective exploiting bounded treewidth in input instances for which an algorithm that runs single exponential in the treewidth is known. The treewidth of an instance is at most the number of its variables, but often much smaller. While our approach suffers from the theoretical worst case bounds, we illustrate how it can still fruitfully be used in combination with modern hardware that takes advantage of parallelism. Our results are encouraging in the sense that also complex reasoning problems can be tackled by parameterized algorithms executed on the GPU or within database systems if instances have small treewidth (<40).