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.', in 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) : February 28–March 3, 2018, Caen, France. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 49:1-49:14. Leibniz International Proceedings in Informatics (LIPIcs). (96).

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:Book chapter
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
(581Kb)
Status:Peer-reviewed
Publisher Web site:http://drops.dagstuhl.de/opus/volltexte/2018/8488/
Publisher statement:© Benoît Larose, Barnaby Martin, and Daniël Paulusma; licensed under Creative Commons License CC-BY
Date accepted:07 January 2018
Date deposited:05 March 2018
Date of first online publication:February 2018
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar