TR05-033 Authors: Martin Furer, Shiva Prasad Kasiviswanathan

Publication: 22nd March 2005 16:03

Downloads: 3996

Keywords:

An algorithm is presented for counting the number of maximum weight satisfying assignments of a 2SAT formula. The worst case running time of $O(\mbox{poly($n$)} \cdot 1.2461^n)$ for formulas with $n$ variables improves on the previous bound of $O(\mbox{poly($n$)} \cdot 1.2561^n)$ by Dahll\"of, Jonsson, and Wahlstr\"om . The weighted 2SAT counting algorithm can be applied to obtain faster algorithms for many combinatorial counting problems, including those of counting maximum weighted independent sets, exact covers, weighted set packings. The above result when combined with a better partitioning technique for domains, leads to improved running times for counting the number of solutions of binary constraint satisfaction problems. Also presented is an improved algorithm for counting 3-colorings in a graph. The upper bound of O$(\mbox{poly($n$)} \cdot {1.7702}^n$) for graphs with $n$ vertices improves on the previous bound of O$(\mbox{poly($n$)} \cdot {1.7879}^n)$ by Angelsmark, and Jonsson.