The paper Centrality Heuristics for Exact Model Counting by Bernhard Bliem and Matti Järvisalo of the Constraint Reasoning and Optimization group has been accepted for publication in the proceedings of the IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI 2019).
Model counting is the archetypical #P-complete problem consisting of determining the number of satisfying truth assignments of a given propositional formula. The authors empirically investigate the potential of employing graph centrality measures as a basis of search heuristics in the context of exact model counting. In particular, the authors integrate centrality-based heuristics into the search-based exact model counter sharpSAT, and show that employing centrality information significantly improves the empirical performance of sharpSAT, and also allows for simplifying the search heuristics compared to the current default heuristics of the model counter.