We prove #P-completeness for counting the number of forests in regular graphs and chordal graphs. We also present algorithms for this problem, running in O*(1.8494(m)) time for 3-regular graphs, and O*(1.9706(m)) time...
详细信息
We prove #P-completeness for counting the number of forests in regular graphs and chordal graphs. We also present algorithms for this problem, running in O*(1.8494(m)) time for 3-regular graphs, and O*(1.9706(m)) time for unit interval graphs, where m is the number of edges in the graph and O*-notation ignores a polynomial factor. The algorithms can be generalized to the Tutte polynomial computation.
We introduce a problem class we call Polynomial Constraint Satisfaction Problems, or PCSP. Where the usual CSPs from computer science and optimization have real-valued score functions, and partition functions from phy...
详细信息
We introduce a problem class we call Polynomial Constraint Satisfaction Problems, or PCSP. Where the usual CSPs from computer science and optimization have real-valued score functions, and partition functions from physics have monomials, PCSP has scores that are arbitrary multivariate formal polynomials, or indeed take values in an arbitrary ring. Although PCSP is much more general than CSP, remarkably, all (exact, exponential-time) algorithms we know of for 2-CSP (where each score depends on at most 2 variables) extend to 2-PCSP, at the expense of just a polynomial factor in running time. Specifically, we extend the reduction-based algorithm of Scott and Sorkin [2007];the specialization of that approach to sparse random instances, where the algorithm runs in polynomial expected time;dynamic-programming algorithms based on tree decompositions;and the split-and-list matrix-multiplication algorithm of Williams [2004]. This gives the first polynomial-space exact algorithm more efficient than exhaustive enumeration for the well-studied problems of finding a maximum bisection of a graph, and calculating the partition function of an Ising model. It also yields the most efficient algorithm known for certain instances of counting and/or weighted Maximum Independent Set. Furthermore, PCSP solves both optimization and counting versions of a wide range of problems, including all CSPs, and thus enables samplers including uniform sampling of optimal solutions and Gibbs sampling of all solutions.
We prove #P-completeness for counting the number of forests in regular graphs and chordal graphs. We also present algorithms for this problem, running in O* (1.8494m) time for 3-regular graphs, and O* (1.9706m) time f...
详细信息
ISBN:
(纸本)9781920682460
We prove #P-completeness for counting the number of forests in regular graphs and chordal graphs. We also present algorithms for this problem, running in O* (1.8494m) time for 3-regular graphs, and O* (1.9706m) time for unit interval graphs, where m is the number of edges in the graph and O*-notation ignores a polynomial factor. The algorithms can be generalized to the Tutte polynomial computation.
The Exact Satisfiability problem is to determine if a CNF-formula has a truth assignment satisfying exactly one literal in each clause;Exact 3-Satisfiability is the version in which each clause contains at most three ...
详细信息
The Exact Satisfiability problem is to determine if a CNF-formula has a truth assignment satisfying exactly one literal in each clause;Exact 3-Satisfiability is the version in which each clause contains at most three literals. In this paper, we present algorithms for Exact Satisfiability and Exact 3-Satisfiability running in time O(2(0.2325n)) and O(2(0.1379n)), respectively. The previously best. algorithms have running times O(2(0.2441n)) for Exact Satisfiability (Methods Oper. Res. 43 (1981) 419-431) and O(2(0.1626n)) for Exact 3-Satisfiability (Annals of Mathematics and Artificial Intelligence 43 (1) (2005) 173-193 and Zapiski nauchnyh seminarov POMI 293 (2002) 118-128). We extend the case analyses of these papers and observe that a formula not satisfying any of our cases has a small number of variables, for which we can try all possible truth assignments and for each such assignment solve the remaining part of the formula in polynomial time. (c) 2005 Elsevier B.V. All rights reserved.
We present four polynomial space and exponentialtimealgorithms for variants of the EXACT SATISFIABILITY problem. First, an O(1.1120(n)) (where n is the number of variables) timealgorithm for the NP-complete decisio...
详细信息
We present four polynomial space and exponentialtimealgorithms for variants of the EXACT SATISFIABILITY problem. First, an O(1.1120(n)) (where n is the number of variables) timealgorithm for the NP-complete decision problem of EXACT 3-SATISFIABILITY, and then an O(1.1907(n)) timealgorithm for the general decision problem of EXACT SATISFIABILITY. The best previous algorithms run in O(1.1193(n)) and O(1.2299(n)) time, respectively. For the #P-complete problem of counting the number of models for EXACT 3-SATISFIABILITY we present an O(1.1487(n)) timealgorithm. We also present an O(1.2190(n)) timealgorithm for the general problem of counting the number of models for EXACT SATISFIABILITY;presenting a simple reduction, we show how this algorithm can be used for computing the permanent of a 0/1 matrix. (C) 2004 Elsevier B.V. All rights reserved.
暂无评论