Dichotomy for tree-structured trigraph list homomorphism problems

Details Dichotomy for tree-structured trigraph list homomorphism problems Dichotomy for tree-structured trigraph list homomorphism problems

2010-09-02

arxiv.org/abs/1009.0358v1

Computer Science

Computational Complexity

Scientific paper

Trigraph list homomorphism problems (also known as list matrix partition problems) have generated recent interest, partly because there are concrete problems that are not known to be polynomial time solvable or NP-complete. Thus while digraph list homomorphism problems enjoy dichotomy (each problem is NP-complete or polynomial time solvable), such dichotomy is not necessarily expected for trigraph list homomorphism problems. However, in this paper, we identify a large class of trigraphs for which list homomorphism problems do exhibit a dichotomy. They consist of trigraphs with a tree-like structure, and, in particular, include all trigraphs whose underlying graphs are trees. In fact, we show that for these tree-like trigraphs, the trigraph list homomorphism problem is polynomially equivalent to a related digraph list homomorphism problem. We also describe a few examples illustrating that our conditions defining tree-like trigraphs are not unnatural, as relaxing them may lead to harder problems.

Affiliated with

Also associated with

No associations

Rating

Dichotomy for tree-structured trigraph list homomorphism problems 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 Dichotomy for tree-structured trigraph list homomorphism problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dichotomy for tree-structured trigraph list homomorphism problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-375683