A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights

Details A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights

2010-08-05

arxiv.org/abs/1008.0915v1

Computer Science

Computational Complexity

Scientific paper

The complexity of graph homomorphism problems has been the subject of intense study. It is a long standing open problem to give a (decidable) complexity dichotomy theorem for the partition function of directed graph homomorphisms. In this paper, we prove a decidable complexity dichotomy theorem for this problem and our theorem applies to all non-negative weighted form of the problem: given any fixed matrix A with non-negative algebraic entries, the partition function Z_A(G) of directed graph homomorphisms from any directed graph G is either tractable in polynomial time or #P-hard, depending on the matrix A. The proof of the dichotomy theorem is combinatorial, but involves the definition of an infinite family of graph homomorphism problems. The proof of its decidability is algebraic using properties of polynomials.

Affiliated with

Also associated with

No associations

Rating

A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights 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 A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-438087