Graph homomorphisms with complex values: a dichotomy theorem
From MaRDI portal
Abstract: Graph homomorphism has been studied intensively. Given an m x m symmetric matrix A, the graph homomorphism function is defined as [Z_A (G) = sum_{f:V->[m]} prod_{(u,v)in E} A_{f(u),f(v)}, ] where G = (V,E) is any undirected graph. The function Z_A can encode many interesting graph properties, including counting vertex covers and k-colorings. We study the computational complexity of Z_A for arbitrary symmetric matrices A with algebraic complex values. Building on work by Dyer and Greenhill, Bulatov and Grohe, and especially the recent beautiful work by Goldberg, Grohe, Jerrum and Thurley, we prove a complete dichotomy theorem for this problem. We show that Z_A is either computable in polynomial-time or #P-hard, depending explicitly on the matrix A. We further prove that the tractability criterion on A is polynomial-time decidable.
Recommendations
- Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- scientific article; zbMATH DE number 1445311
- A complexity dichotomy for partition functions with mixed signs
- A complexity dichotomy for hypergraph partition functions
Cited in
(48)- Dichotomy for Holant\(^\ast\) problems on the Boolean domain
- 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
- A dichotomy for bounded degree graph homomorphisms with nonnegative weights
- Dichotomy theorems for homomorphism polynomials of graph classes
- A complete dichotomy rises from the capture of vanishing signatures
- A dichotomy theorem for homomorphism polynomials
- The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
- Counting 4 4 matrix partitions of graphs
- Holant problems for 3-regular graphs with complex edge functions
- Nonnegative weighted \#CSP: an effective complexity dichotomy
- On tractable exponential sums
- Homeomorphism of 2-Complexes is Graph Isomorphism Complete
- The complexity of Boolean Holant problems with nonnegative weights
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- A collapse theorem for holographic algorithms with matchgates on domain size at most 4
- Counting constraint satisfaction problems
- A complete dichotomy for complex-valued \(\textsc{Holant}^c\)
- Counting homomorphisms to trees modulo a prime
- On a theorem of Lovász that \((\cdot, H)\) determines the isomorphism type of \(H\)
- A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation
- Dichotomy Theorems for Homomorphism Polynomials of Graph Classes
- Perfect matchings, rank of connection tensors and graph homomorphisms
- A complexity dichotomy for partition functions with mixed signs
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- Holographic algorithms with matchgates capture precisely tractable planar \#CSP
- Perfect matchings, rank of connection tensors and graph homomorphisms
- Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
- Complexity classification of the eight-vertex model
- The computational complexity of Holant problems on 3-regular graphs
- A complexity dichotomy for hypergraph partition functions
- The complexity of counting planar graph homomorphisms of domain size 3
- A complexity trichotomy for k-regular asymmetric spin systems with complex edge functions
- The complexity of ferromagnetic 2-spin systems on bounded degree graphs
- On the complexity of generalized chromatic polynomials
- Computing the partition function for graph homomorphisms
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- A dichotomy for bounded degree graph homomorphisms with nonnegative weights
- From holant to quantum entanglement and back
- Equality on all \#CSP instances yields constraint function isomorphism via interpolation and intertwiners
- Two-state spin systems with negative interactions
- Two-state spin systems with negative interactions
- Dichotomy for non-negative valued Holant problems on 3-regular bipartite graphs
- On the complexity of \#CSP\(^d\)
- On counting (quantum-)graph homomorphisms in finite fields of prime order
- Computing the partition function for graph homomorphisms with multiplicities
This page was built for publication: Graph homomorphisms with complex values: a dichotomy theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5891164)
