Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials

DOI10.1137/16M1101003zbMath1383.68099MaRDI QIDQ4602373

Viresh Patel, Guus Regts

Publication date: 10 January 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

partition functiongraph homomorphismTutte polynomialapproximation algorithmsindependence polynomialHolant problem

Mathematics Subject Classification ID

Graph polynomials (05C31) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (50)

On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs ⋮ Uniqueness of the Gibbs measure for the 4-state anti-ferromagnetic Potts model on the regular tree ⋮ The complexity of approximating the complex-valued Potts model ⋮ Rapid Mixing of Glauber Dynamics up to Uniqueness via Contraction ⋮ Approximately Counting Independent Sets of a Given Size in Bounded-Degree Graphs ⋮ Approximating real-rooted and stable polynomials, with combinatorial applications ⋮ A Spectral Independence View on Hard Spheres via Block Dynamics ⋮ Zero-freeness and approximation of real Boolean Holant problems ⋮ Lee-Yang zeros of the antiferromagnetic Ising model ⋮ Zeros and approximations of holant polynomials on the complex plane ⋮ Algorithmic Pirogov-Sinai theory ⋮ Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing ⋮ Fast mixing via polymers for random graphs with unbounded degree ⋮ Absence of zeros implies strong spatial mixing ⋮ Smoothed counting of 0–1 points in polyhedra ⋮ Combinatorics. Abstracts from the workshop held January 1--7, 2023 ⋮ Fast algorithms at low temperatures via Markov chains† ⋮ Correlation decay and the absence of zeros property of partition functions ⋮ Uniqueness of the Gibbs measure for the anti-ferromagnetic Potts model on the infinite \(\Delta \)-regular tree for large \(\Delta \) ⋮ Algorithms for hard-constraint point processes via discretization ⋮ Approximating the chromatic polynomial is as hard as computing it exactly ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Zeros, chaotic ratios and the computational complexity of approximating the independence polynomial ⋮ Large scale stochastic dynamics. Abstracts from the workshop held September 15--21, 2019 ⋮ Inapproximability of the Independent Set Polynomial in the Complex Plane ⋮ The Ising partition function: zeros and deterministic approximation ⋮ Location of zeros for the partition function of the Ising model on bounded degree graphs ⋮ Algorithms for #BIS-Hard Problems on Expander Graphs ⋮ Some applications of Wagner's weighted subgraph counting polynomial ⋮ Computing the number of induced copies of a fixed graph in a bounded degree graph ⋮ Cayley trees do not determine the maximal zero-free locus of the independence polynomial ⋮ Counting independent sets in graphs with bounded bipartite pathwidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On a conjecture of Sokal concerning roots of the independence polynomial ⋮ Fisher zeros and correlation decay in the Ising model ⋮ Stability and complexity of mixed discriminants ⋮ Testing for Dense Subsets in a Graph via the Partition Function ⋮ Weighted counting of solutions to sparse systems of equations ⋮ Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems ⋮ Fisher Zeros and Correlation Decay in the Ising Model ⋮ Computing permanents of complex diagonally dominant matrices and tensors ⋮ More on zeros and approximation of the Ising partition function ⋮ The complexity of approximating the complex-valued Potts model ⋮ Efficient algorithms for approximating quantum partition functions ⋮ Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model ⋮ The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs ⋮ Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computing the permanent of (some) complex matrices
• Tensor invariants for certain subgroups of the orthogonal group
• Correlation decay and deterministic FPTAS for counting colorings of a graph
• Combinatorics and complexity of partition functions
• Computing the partition function for graph homomorphisms
• Graph invariants related to statistical mechanical models: Examples and problems
• 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
• Computing the number of induced copies of a fixed graph in a bounded degree graph
• Zero-free regions of partition functions with applications to algorithms and graph limits
• Complex zero-free regions at large \(|q|\) for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
• On a conjecture of Sokal concerning roots of the independence polynomial
• The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
• On the number of \(B\)-flows of a graph
• Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
• The complexity of partition functions
• A Personal List of Unsolved Problems Concerning Lattice Gases and Antiferromagnetic Potts Models
• Improved bounds for sampling colorings
• The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation)
• Improved FPTAS for Multi-spin Systems
• Counting independent sets up to the tree threshold
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• From Holant to #CSP and Back: Dichotomy for Holant c Problems
• Computational Complexity of Holant Problems
• Polynomial-Time Approximation Algorithms for the Ising Model
• Computing the partition function for cliques in a graph
• Approximating the Partition Function of the Ferromagnetic Potts Model
• Edge coloring models and reflection positivity
• On Approximately Counting Colorings of Small Degree Graphs
• Approximating permanents and hafnians
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Left and right convergence of graphs with bounded degree
• On Markov Chains for Independent Sets
• A Simple FPTAS for Counting Edge Covers
• A complete dichotomy rises from the capture of vanishing signatures
• Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem

This page was built for publication: Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials