Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function

DOI10.1145/1597036.1597049MaRDI QIDQ2930272zbMATH OpenOpenAlexFDO

Authors Gregory B. Sorkin, Alex Scott

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cs/0604079

zbMATH Keywords

constraint satisfactiondiscrete optimizationexact algorithmexponential-time algorithmgenerating functionpartition function

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Abstract: 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.

Recommendations

• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• An LP-Designed Algorithm for Constraint Satisfaction
• Faster algorithms for MAX CUT and MAX CSP, with polynomial expected time for sparse instances
• Solving partial constraint satisfaction problems with tree decomposition
• New exact algorithms for the 2-constraint satisfaction problem

Cited in

(10)

• \(H\)-colouring \(P_t\)-free graphs in subexponential time
• Bipartition polynomials, the Ising model, and domination in graphs
• Tractability in constraint satisfaction problems: a survey
• Separate, measure and conquer: faster polynomial-space algorithms for Max 2-CSP and counting dominating sets
• Solving partial constraint satisfaction problems with tree decomposition
• A general reduction theorem with applications to pathwidth and the complexity of Max 2-CSP
• Efficient algorithms for three‐dimensional axial and planar random assignment problems
• Faster graph coloring in polynomial space
• Optimal sufficient requirements on the embedded Ising problem in polynomial time
• A faster polynomial-space algorithm for Max 2-CSP

This page was built for publication: Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2930272)