Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Surjective H-Colouring over reflexive digraphs.

Larose, B. and Martin, B. and Paulusma, D. (2018) 'Surjective H-Colouring over reflexive digraphs.', ACM transactions on computation theory., 11 (1). p. 3.

Abstract

The Surjective H-Colouring problem is to test if a given graph allows a vertex-surjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive graphs. We introduce endo-triviality, the property of a structure that all of its endomorphisms that do not have range of size 1 are automorphisms, as a means to obtain complexity-theoretic classifications of Surjective H-Colouring in the case of reflexive digraphs. Chen (2014) proved, in the setting of constraint satisfaction problems, that Surjective H-Colouring is NP-complete if H has the property that all of its polymorphisms are essentially unary. We give the first concrete application of his result by showing that every endo-trivial reflexive digraph H has this property. We then use the concept of endo-triviality to prove, as our main result, a dichotomy for Surjective H-Colouring when H is a reflexive tournament: if H is transitive, then Surjective H-Colouring is in NL; otherwise, it is NP-complete. By combining this result with some known and new results, we obtain a complexity classification for Surjective H-Colouring when H is a partially reflexive digraph of size at most 3.

Item Type:Article
Full text:(AM) Accepted Manuscript
Download PDF
(890Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1145/3282431
Publisher statement:© 2018 Association for Computing Machinery. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM transactions on computation theory, https://doi.org/10.1145/3282431
Date accepted:08 September 2018
Date deposited:11 September 2018
Date of first online publication:30 November 2018
Date first made open access:30 November 2018

Save or Share this output

Export:
Export
Look up in GoogleScholar