Enumerating Homomorphisms
| dc.creator | Bulatov, Andrei A. | |
| dc.creator | Dalmau, Victor | |
| dc.creator | Grohe, Martin | |
| dc.creator | Marx, Daniel | |
| dc.date | 2009-02-07 | |
| dc.date.accessioned | 2026-07-07T12:39:20Z | |
| dc.date.available | 2026-07-07T12:39:20Z | |
| dc.description | 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. | |
| dc.identifier | https://arxiv.org/abs/0902.1256 | |
| dc.identifier | http://arxiv.org/abs/0902.1256 | |
| dc.identifier | 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 231-242 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/219073 | |
| dc.subject | Computational Complexity | |
| dc.subject | Logic in Computer Science | |
| dc.title | Enumerating Homomorphisms | |
| dc.type | text |