On counting homomorphisms to directed acyclic graphs

DOI10.1145/1314690.1314691zbMath1312.68098OpenAlexW2145707075WikidataQ56323861 ScholiaQ56323861MaRDI QIDQ3546354

Leslie Ann Goldberg, Martin Dyer, Mike S. Paterson

Publication date: 21 December 2008

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1314690.1314691

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (27)

Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Holant problems for 3-regular graphs with complex edge functions ⋮ Classification of a Class of Counting Problems Using Holographic Reductions ⋮ The Complexity of Boolean Holant Problems with Nonnegative Weights ⋮ Holographic reduction, interpolation and hardness ⋮ Partition functions on \(k\)-regular graphs with \(\{0,1\}\)-vertex assignments and real edge functions ⋮ The complexity of complex weighted Boolean \#CSP ⋮ The complexity of approximating bounded-degree Boolean \(\#\)CSP ⋮ From Holant to \#CSP and back: dichotomy for Holant\(^{c}\) problems ⋮ A dichotomy for bounded degree graph homomorphisms with nonnegative weights ⋮ Enumerating homomorphisms ⋮ The complexity of weighted and unweighted \(\#\)CSP ⋮ Unnamed Item ⋮ Holographic algorithms beyond matchgates ⋮ Counting polygon triangulations is hard ⋮ On the Complexity of Holant Problems ⋮ Spin systems on \(k\)-regular graphs with complex edge functions ⋮ A computational proof of complexity of some restricted counting problems ⋮ Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP ⋮ Unnamed Item ⋮ Dichotomy for Holant\(^\ast\) problems on the Boolean domain ⋮ The Complexity of Symmetric Boolean Parity Holant Problems ⋮ A Complete Dichotomy Rises from the Capture of Vanishing Signatures ⋮ Approximate Counting via Correlation Decay in Spin Systems ⋮ A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights ⋮ Classical simulation of quantum circuits by half Gauss sums ⋮ A dichotomy for real weighted Holant problems

This page was built for publication: On counting homomorphisms to directed acyclic graphs