B. Larose
Surjective H-Colouring over Reflexive Digraphs
Larose, B.; Martin, B.; Paulusma, D.
Authors
Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor
Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor
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
Published Conference Proceeding
(594 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Benoît Larose, Barnaby Martin, and Daniël Paulusma; licensed under Creative Commons License CC-BY
You might also like
The lattice and semigroup structure of multipermutations
(2021)
Journal Article
Constraint satisfaction problems for reducts of homogeneous graphs
(2019)
Journal Article
Surjective H-Colouring over reflexive digraphs
(2018)
Journal Article
On the Complexity of the Model Checking Problem
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search