Graph Homomorphisms with Complex Values: A Dichotomy Theorem

Details Graph Homomorphisms with Complex Values: A Dichotomy Theorem Graph Homomorphisms with Complex Values: A Dichotomy Theorem

2009-03-27

arxiv.org/abs/0903.4728v2

Computer Science

Computational Complexity

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Graph Homomorphisms with Complex Values: A Dichotomy Theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph Homomorphisms with Complex Values: A Dichotomy Theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph Homomorphisms with Complex Values: A Dichotomy Theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-21220