Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-033 | 5th March 2005 00:00

Algorithms for Counting 2-SAT Solutions and Colorings with Applications


Authors: Martin Furer, Shiva Prasad Kasiviswanathan
Publication: 22nd March 2005 16:03
Downloads: 2036


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.

ISSN 1433-8092 | Imprint