Enumerating Homomorphisms

Details Enumerating Homomorphisms Enumerating Homomorphisms

2009-02-07

arxiv.org/abs/0902.1256v1

26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 231-242

Computer Science

Computational Complexity

Scientific paper

The homomorphism problem for relational structures is an abstract way of formulating constraint satisfaction problems (CSP) and various problems in database theory. The decision version of the homomorphism problem received a lot of attention in literature; in particular, the way the graph-theoretical structure of the variables and constraints influences the complexity of the problem is intensively studied. Here we study the problem of enumerating all the solutions with polynomial delay from a similar point of view. It turns out that the enumeration problem behaves very differently from the decision version. We give evidence that it is unlikely that a characterization result similar to the decision version can be obtained. Nevertheless, we show nontrivial cases where enumeration can be done with polynomial delay.

Affiliated with

Also associated with

No associations

Rating

Enumerating Homomorphisms 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 Enumerating Homomorphisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enumerating Homomorphisms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-312183