The complexity of approximating bounded-degree Boolean \(\#\)CSP

DOI10.1016/j.ic.2011.12.007zbMath1282.68136OpenAlexW1966841310WikidataQ56323824 ScholiaQ56323824MaRDI QIDQ1932171

David Richerby, Leslie Ann Goldberg, Markus Jalsenius, Martin Dyer

Publication date: 17 January 2013

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2011.12.007

zbMATH Keywords

complexityapproximation algorithmCSPcounting constraint satisfaction problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items

Zero-freeness and approximation of real Boolean Holant problems, The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs, Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems, On the Complexity of Holant Problems, Counting Constraint Satisfaction Problems.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• A unified theory of structural tractability for constraint satisfaction problems
• An approximation trichotomy for Boolean \#CSP
• Random generation of combinatorial structures from a uniform distribution
• On the complexity of H-coloring
• Tree clustering for constraint networks
• Conjunctive-query containment and constraint satisfaction
• Counting \(H-\)colorings of partial \(k-\)trees
• Networks of constraints: Fundamental properties and applications to picture processing
• The relative complexity of approximate counting problems
• Complexity of generalized satisfiability counting problems
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• An Effective Dichotomy for the Counting Constraint Satisfaction Problem
• Counting independent sets up to the tree threshold
• On the Approximation Complexity Hierarchy
• On Counting Independent Sets in Sparse Graphs
• Corrigendum: The complexity of counting graph homomorphisms
• The Complexity of the Counting Constraint Satisfaction Problem
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• On counting homomorphisms to directed acyclic graphs
• The Complexity of Weighted Boolean #CSP
• The Complexity of Enumeration and Reliability Problems
• On the Structure of Polynomial Time Reducibility
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Fast convergence of the Glauber dynamics for sampling independent sets
• On Markov Chains for Independent Sets
• Holant problems and counting CSP
• The complexity of satisfiability problems
• Mathematical Foundations of Computer Science 2003
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Fanout limitations on constraint systems