The complexity of surjective homomorphism problems - a survey

Article


Bodirsky, M., Kara, J. and Martin, B. 2012. The complexity of surjective homomorphism problems - a survey. Discrete Applied Mathematics. 160 (12), pp. 1680-1690.
TypeArticle
TitleThe complexity of surjective homomorphism problems - a survey
AuthorsBodirsky, M., Kara, J. and Martin, B.
Abstract

We survey known results about the complexity of surjective homomorphism problems, studied in the context of related problems in the literature such as list homomorphism, retraction and compaction. In comparison with these problems, surjective homomorphism problems seem to be harder to classify and we examine especially three concrete problems that have arisen from the literature, two of whose complexity remains open.

Keywordssurjective homomorphisms; computational complexity; constraint satisfaction
Research GroupFoundations of Computing group
PublisherElsevier
JournalDiscrete Applied Mathematics
ISSN0166-218X
Publication dates
PrintAug 2012
Online19 Apr 2012
Publication process dates
Deposited13 Dec 2012
Accepted24 Mar 2012
Output statusPublished
Web address (URL)http://dx.doi.org/10.1016/j.dam.2012.03.029
LanguageEnglish
Permalink -

https://repository.mdx.ac.uk/item/83wz2

  • 34
    total views
  • 0
    total downloads
  • 0
    views this month
  • 0
    downloads this month

Export as