Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials

DOI10.1016/j.endm.2017.07.061zbMath1378.05099arXiv1607.01167OpenAlexW2793605908MaRDI QIDQ1690044

Viresh Patel, Guus Regts

Publication date: 18 January 2018

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

zbMATH Keywords

partition functionTutte polynomialapproximation algorithmsindependence polynomialHolant problem

Mathematics Subject Classification ID

Graph polynomials (05C31) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)

Related Items (10)

An FPTAS for the hardcore model on random regular bipartite graphs ⋮ Counting Independent Sets and Colorings on Random Regular Bipartite Graphs ⋮ Approximating permanents and hafnians ⋮ A fixed-parameter perspective on \#BIS ⋮ Unnamed Item ⋮ Zero-free regions of partition functions with applications to algorithms and graph limits ⋮ Unnamed Item ⋮ Gauges, loops, and polynomials for partition functions of graphical models ⋮ Implementations and the independent set polynomial below the Shearer threshold ⋮ Polymer dynamics via cliques: new conditions for approximations

Cites Work

• Unnamed Item
• The roots of the independence polynomial of a clawfree graph
• Computing the partition function for graph homomorphisms with multiplicities
• Benjamini-Schramm continuity of root moments of graph polynomials
• On a problem of Spencer
• Zeros of chromatic and flow polynomials of graphs
• Complex zero-free regions at large \(|q|\) for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• Improved bounds for sampling colorings
• Improved FPTAS for Multi-spin Systems
• Counting independent sets up to the tree threshold
• Computing the partition function for cliques in a graph
• An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
• Approximating permanents and hafnians
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• On Markov Chains for Independent Sets

This page was built for publication: Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials