Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430100 | Journal of Computer and System Sciences | 2012 | 13 Pages |
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.
► We study the problem of enumerating all solutions of a CSP with polynomial delay. ► We focus on structural or left-hand restrictions. ► We provide evidence that a complete characterization is hard. ► We obtain nontrivial cases where enumeration can be done with polynomial delay.