ECCC-Report TR05-033https://eccc.weizmann.ac.il/report/2005/033Comments and Revisions published for TR05-033en-usTue, 22 Mar 2005 16:03:59 +0200
Paper TR05-033
| Algorithms for Counting 2-SAT Solutions and Colorings with Applications |
Martin Furer,
Shiva Prasad Kasiviswanathan
https://eccc.weizmann.ac.il/report/2005/033An 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.
Tue, 22 Mar 2005 16:03:59 +0200https://eccc.weizmann.ac.il/report/2005/033