
Model counting is the #P problem of counting the number of satisfying solutions of a given propositional formula. Here we focus on a restricted variant of this problem, where the input formula is monotone (i.e., there are no negations). A monotone conjunctive normal form (CNF) formula is sufficient for modeling various graph problems, e.g., the vertex covers of a graph. Even for this restricted case, there is no known efficient approximation scheme. We show that the classical Spectra technique that is widely used in network reliability can be adapted for counting monotone CNF formulas. We prove that the proposed algorithm is logarithmically efficient for random monotone 2-CNF instances. Although we do not prove the efficiency of Spectra for k-CNF where k > 2, our experiments show that it is effective in practice for such formulas.
Counting, Analysis of algorithms and problem complexity, Random graphs (graph-theoretic aspects), 511, Combinatorics in computer science, Monte Carlo methods, 1803 Management Science and Operations Research, 1710 Information Systems, Monotone CNF, simulation, 1712 Software, monotone CNF, Graph theory (including graph drawing) in computer science, 1706 Computer Science Applications, counting, Monte Carlo, Simulation, random graphs, Random graphs
Counting, Analysis of algorithms and problem complexity, Random graphs (graph-theoretic aspects), 511, Combinatorics in computer science, Monte Carlo methods, 1803 Management Science and Operations Research, 1710 Information Systems, Monotone CNF, simulation, 1712 Software, monotone CNF, Graph theory (including graph drawing) in computer science, 1706 Computer Science Applications, counting, Monte Carlo, Simulation, random graphs, Random graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
