The Complexity of Approximately Counting Tree Homomorphisms

DOI10.1145/2600917zbMath1321.68312arXiv1305.6306OpenAlexW3105782517MaRDI QIDQ2943573

Leslie Ann Goldberg, Mark R. Jerrum

Publication date: 3 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

reducibilitygraph homomorphismscomplexity classescounting problems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs in time-dependent statistical mechanics (82C20) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Approximately counting locally-optimal structures, Unnamed Item, Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation trichotomy for Boolean \#CSP
• Random generation of combinatorial structures from a uniform distribution
• Polynomial graph-colorings
• Hereditarily hard \(H\)-colouring problems
• The relative complexity of approximate counting problems
• Counting and sampling \(H\)-colourings
• Complexity of tree homomorphisms
• Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
• On Markov Chains for Randomly H-Coloring a Graph
• Polynomial-Time Approximation Algorithms for the Ising Model
• The Complexity of Ferromagnetic Ising with Local Fields
• Approximating the Partition Function of the Ferromagnetic Potts Model
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Complexity of Multiterminal Cuts
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• On the computational complexity of the Jones and Tutte polynomials
• The expressibility of functions on the boolean domain, with applications to counting CSPs
• On Unapproximable Versions of $NP$-Complete Problems