On counting homomorphisms to directed acyclic graphs

DOI10.1145/1314690.1314691zbMath1312.68098WikidataQ56323861 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

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

05C20: Directed graphs (digraphs), tournaments

05C60: Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)

Related Items

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