A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
We give an algorithm for counting the number of max-weight solutions to a 2SAT formula, and improve the bound on its running time to Open image in new window . The main source of the improvement is a refinement of the method of analysis, where we extend t
- PDF / 219,564 Bytes
- 12 Pages / 430 x 660 pts Page_size
- 34 Downloads / 141 Views
bstract. We give an algorithm for counting the number of max-weight solutions to a 2SAT formula, and improve the bound on its running time to O (1.2377n ). The main source of the improvement is a refinement of the method of analysis, where we extend the concept of compound (piecewise linear) measures to multivariate measures, also allowing the optimal parameters for the measure to be found automatically. This method extension should be of independent interest.
1
Introduction
From a computational complexity point of view, the problem class #P of problems where you want to know the number of solutions to some problem in NP is a very difficult one. The class was proposed by Valiant in the 1970’s [14], and it was later proved that the so-called polynomial hierarchy is contained in P #P [12] (i.e. that a polynomial-time algorithm for any #P-complete problem would allow us to solve any problem in the polynomial hierarchy in polynomial time; in fact, a single query to the algorithm would suffice). #P-complete problems include the counting counterparts of both NP-complete problems such as 3SAT (counting counterpart #3SAT) and problems that are in P. The problem considered in this paper, #2SAT, is an example of the latter: the “decision variant” 2SAT is a well-known polynomial problem, while the counting version #2SAT is #P-complete [9, 13]. However, despite the apparent difficulty of the class, individual #P-complete problems can be solved in reasonable exponential time; for instance, the bound O∗ (1.2377n)1 for #2SAT is significantly faster than any bound for solving 3SAT (for which the best bounds are a probabilistic algorithm with a bound of O∗ (1.3238n) by Iwama and Tamaki [8], and a deterministic algorithm with a bound of O∗ (1.473n) by Brueggemann and Kern [1]). One of the first algorithms for a counting problem came in the early 1960’s with Ryser’s [11] O(n2 2n ) time algorithm for counting the number of perfect matchings in a bipartite graph (also known as computing the permanent of a 0/1 matrix). Previous work on the #2SAT problem with better bounds than of, O∗ (2n ) includes results by Dubois [4], Zhang [17], Littman et al. [10], Dahll¨ Jonsson and Wahlstr¨ om [2, 3], and F¨ urer and Kasiviswanathan [7]. In terms 1
O∗ (·), Θ∗ (·), etc, signify that polynomial factors are ignored.
M. Grohe and R. Niedermeier (Eds.): IWPEC 2008, LNCS 5018, pp. 202–213, 2008. c Springer-Verlag Berlin Heidelberg 2008
A Tighter Bound for Counting Max-Weight Solutions to 2SAT Instances
203
of the actual bounds, the bound O∗ (1.3247n) appeared in [2]; later, a complete rewrite of the algorithm for the journal version produced the bound O∗ (1.2561n) [3], where the method of compound measures was introduced (under the name of piecewise linear measures); and the previously best bound O∗ (1.2461n) [7] was produced by a more detailed version of the analysis in [3]. The bound O∗ (1.2377n) produced in this paper is the result of a further improvement of the analysis through compound measures, this time introducing multi-variate compound measur
Data Loading...
