License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2009.1838
URN: urn:nbn:de:0030-drops-18385
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/1838/
Go to the corresponding LIPIcs Volume Portal

Bulatov, Andrei A. ; Dalmau, Victor ; Grohe, Martin ; Marx, Daniel

Enumerating Homomorphisms

pdf-format:
09001.BulatovAndrei.1838.pdf (0.1 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{bulatov_et_al:LIPIcs:2009:1838,
  author =	{Andrei A. Bulatov and Victor Dalmau and Martin Grohe and Daniel Marx},
  title =	{{Enumerating Homomorphisms}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{231--242},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Susanne Albers and Jean-Yves Marion},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/1838},
  URN =		{urn:nbn:de:0030-drops-18385},
  doi =		{10.4230/LIPIcs.STACS.2009.1838},
  annote =	{Keywords: }
}

Collection: 26th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2009
Date of publication: 19.02.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI