The complexity of approximately counting tree homomorphisms

DOI10.1145/2600917MaRDI QIDQ2943573zbMATHOpenAlexFDO

Authors Leslie Ann Goldberg, Mark 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

complexity classesgraph homomorphismsreducibilitycounting problems

Mathematics Subject Classification ID

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

Abstract: We study two computational problems, parameterised by a fixed tree H. #HomsTo(H) is the problem of counting homomorphisms from an input graph G to H. #WHomsTo(H) is the problem of counting weighted homomorphisms to H, given an input graph G and a weight function for each vertex v of G. Even though H is a tree, these problems turn out to be sufficiently rich to capture all of the known approximation behaviour in #P. We give a complete trichotomy for #WHomsTo(H). If H is a star then #WHomsTo(H) is in FP. If H is not a star but it does not contain a certain induced subgraph J_3 then #WHomsTo(H) is equivalent under approximation-preserving (AP) reductions to #BIS, the problem of counting independent sets in a bipartite graph. This problem is complete for the class #RHPi_1 under AP-reductions. Finally, if H contains an induced J_3 then #WHomsTo(H) is equivalent under AP-reductions to #SAT, the problem of counting satisfying assignments to a CNF Boolean formula. Thus, #WHomsTo(H) is complete for #P under AP-reductions. The results are similar for #HomsTo(H) except that a rich structure emerges if H contains an induced J_3. We show that there are trees H for which #HomsTo(H) is #SAT-equivalent (disproving a plausible conjecture of Kelk). There is an interesting connection between these homomorphism-counting problems and the problem of approximating the partition function of the ferromagnetic Potts model. In particular, we show that for a family of graphs J_q, parameterised by a positive integer q, the problem #HomsTo(H) is AP-interreducible with the problem of approximating the partition function of the q-state Potts model. It was not previously known that the Potts model had a homomorphism-counting interpretation. We use this connection to obtain some additional upper bounds for the approximation complexity of #HomsTo(J_q).

Recommendations

• Counting homomorphisms to trees modulo a prime
• Counting homomorphisms to trees modulo a prime
• Publication:4952624
• scientific article; zbMATH DE number 1545676
• Automata, Languages and Programming

Cites work

• scientific article; zbMATH DE number 1545676 (Why is no real title available?)
• scientific article; zbMATH DE number 2151247 (Why is no real title available?)
• scientific article; zbMATH DE number 3076589 (Why is no real title available?)
• An approximation trichotomy for Boolean \#CSP
• Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
• Complexity of tree homomorphisms
• Counting and sampling \(H\)-colourings
• Hereditarily hard \(H\)-colouring problems
• On Markov chains for randomly \(H\)-coloring a graph
• On Unapproximable Versions of $NP$-Complete Problems
• On sampling colorings of bipartite graphs
• On the computational complexity of the Jones and Tutte polynomials
• Polynomial graph-colorings
• Polynomial-Time Approximation Algorithms for the Ising Model
• Random generation of combinatorial structures from a uniform distribution
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• The Complexity of Ferromagnetic Ising with Local Fields
• The Complexity of Multiterminal Cuts
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The expressibility of functions on the Boolean domain, with applications to counting CSPs
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• The relative complexity of approximate counting problems

Cited in

(7)

• Counting and Enumeration Problems with Bounded Treewidth
• Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
• Counting homomorphisms to trees modulo a prime
• Counting homomorphisms to trees modulo a prime
• The complexity of approximately counting retractions
• Counting problems in parameterized complexity
• Approximately counting locally-optimal structures

This page was built for publication: The complexity of approximately counting tree homomorphisms

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