Graph Homomorphisms with Complex Values: A Dichotomy Theorem
From MaRDI portal
Publication:5891164
DOI10.1137/110840194zbMath1275.68073arXiv0903.4728OpenAlexW2570207426MaRDI QIDQ5891164
Jin-Yi Cai, Xi Chen, Pinyan Lu
Publication date: 25 September 2013
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0903.4728
Analysis of algorithms and problem complexity (68Q25) Graph polynomials (05C31) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Perfect matchings, rank of connection tensors and graph homomorphisms, The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems, Nonnegative Weighted #CSP: An Effective Complexity Dichotomy, Holant problems for 3-regular graphs with complex edge functions, The Complexity of Boolean Holant Problems with Nonnegative Weights, A Full Dichotomy for $\hol^{c}$, Inspired by Quantum Computation, Computing the partition function for graph homomorphisms with multiplicities, A dichotomy for bounded degree graph homomorphisms with nonnegative weights, Complexity classification of the eight-vertex model, Unnamed Item, Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials, Unnamed Item, The computational complexity of Holant problems on 3-regular graphs, Holographic algorithms beyond matchgates, Counting Constraint Satisfaction Problems., A collapse theorem for holographic algorithms with matchgates on domain size at most 4, On the complexity of generalized chromatic polynomials, Computing the partition function for graph homomorphisms, Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP, The complexity of planar Boolean \#CSP with complex weights, Dichotomy for Holant\(^\ast\) problems on the Boolean domain, A Complete Dichotomy Rises from the Capture of Vanishing Signatures, Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems, The complexity of counting \(\mathrm{CSP}^d\), A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights, A dichotomy for real weighted Holant problems
