The Complexity of Approximately Counting Tree Homomorphisms

DOI10.1145/2600917zbMATH Open1321.68312arXiv1305.6306OpenAlexW3105782517MaRDI QIDQ2943573FDOQ2943573

Authors: Leslie Ann Goldberg, Mark Jerrum 

Publication date: 3 September 2015

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

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).

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

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

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)

Cites Work

• Title not available (Why is that?)
• Random generation of combinatorial structures from a uniform distribution
• The relative complexity of approximate counting problems
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Complexity of Multiterminal Cuts
• On the computational complexity of the Jones and Tutte polynomials
• 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 expressibility of functions on the boolean domain, with applications to counting CSPs
• On Unapproximable Versions of $NP$-Complete Problems
• An approximation trichotomy for Boolean \#CSP
• On Markov chains for randomly \(H\)-coloring a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• Polynomial graph-colorings
• Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
• Hereditarily hard \(H\)-colouring problems
• Complexity of tree homomorphisms
• Counting and sampling \(H\)-colourings
• The Complexity of Choosing an H-Coloring (Nearly) Uniformly at Random
• On sampling colorings of bipartite graphs

Cited In (4)

• Counting and Enumeration Problems with Bounded Treewidth
• Approximately counting locally-optimal structures
• Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
• Title not available (Why is that?)

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)