Polynomial Constraint Satisfaction, Graph Bisection, and the Ising Partition Function

Details Polynomial Constraint Satisfaction, Graph Bisection, and the Ising Partition Function Polynomial Constraint Satisfaction, Graph Bisection, and the Ising Partition Function

2006-04-20

arxiv.org/abs/cs/0604079v3

ACM Transactions on Algorithms, 5(4):45:1-27, October 2009.

Computer Science

Discrete Mathematics

Another algorithm, some applications, and a general revamping

Scientific paper

10.1145/1597036.1597049

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; 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. This gives the first polynomial-space exact algorithm more efficient than exhaustive enumeration for the well-studied problems of finding a minimum bisection of a graph, and calculating the partition function of an Ising model, and the most efficient algorithm known for certain instances of 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.

Affiliated with

Also associated with

No associations

Rating

Polynomial Constraint Satisfaction, Graph Bisection, and the Ising Partition Function does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Polynomial Constraint Satisfaction, Graph Bisection, and the Ising Partition Function, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Polynomial Constraint Satisfaction, Graph Bisection, and the Ising Partition Function will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-627071