Skip to main content

Research Repository

Advanced Search

Surjective H-Colouring over Reflexive Digraphs

Larose, B.; Martin, B.; Paulusma, D.

Surjective H-Colouring over Reflexive Digraphs Thumbnail


Authors

B. Larose



Contributors

Rolf Niedermeier
Editor

Brigitte Vallée
Editor

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.

Citation

Larose, B., Martin, B., & Paulusma, D. (2018). Surjective H-Colouring over Reflexive Digraphs. In R. Niedermeier, & B. Vallée (Eds.), 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) : February 28–March 3, 2018, Caen, France (49:1-49:14). https://doi.org/10.4230/lipics.stacs.2018.49

Conference Name 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Conference Location Caen, France
Start Date Feb 28, 2023
End Date Mar 3, 2018
Acceptance Date Jan 7, 2018
Publication Date Feb 1, 2018
Deposit Date Mar 5, 2018
Publicly Available Date Mar 29, 2024
Pages 49:1-49:14
Series Title Leibniz International Proceedings in Informatics (LIPIcs)
Series Number 96
Series ISSN 1868-8969
Book Title 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) : February 28–March 3, 2018, Caen, France.
DOI https://doi.org/10.4230/lipics.stacs.2018.49
Public URL https://durham-repository.worktribe.com/output/1145132
Publisher URL http://drops.dagstuhl.de/opus/volltexte/2018/8488/

Files





You might also like



Downloadable Citations