Centrality Heuristics for Exact Model Counting Model counting is the archetypical Pcomplete problem consisting of determining the number of satisfying truth assignments of a given propositional formula. In this short paper, we empirically investigate the potential of employing graph centrality measures as a basis of search heuristics in the context of exact model counting. In particular, we integrate centralitybased heuristics into the searchbased exact model counter sharpSAT. Our experiments 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. In particular, we show that the VSIDS heuristic, which is an integral search heuristic employed in essentially all stateoftheart conflictdriven clause learning Boolean satisfiability solvers, appears to be of very limited use in the context of model counting.

Definability for model counting Abstract   We define and evaluate a new preprocessing technique for propositional model counting. This technique leverages definability, i.e., the ability to determine that some gates are implied by the input formula xcexa3. Such gates can be exploited to simplify xcexa3 without modifying its number of models. Unlike previous techniques based on gate detection and replacement, gates do not need to be made explicit in our approach. Our preprocessing technique thus consists of two phases: computing a bipartition    xe3x80x88  I  ,  O  xe3x80x89    of the variables of xcexa3 where the variables from O are defined in xcexa3 in terms of I, then eliminating some variables of O in xcexa3. Our experiments show the computational benefits which can be achieved by taking advantage of our preprocessing technique for model counting.