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
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. ACM Transactions on Computation Theory, 11(1), Article 3. https://doi.org/10.1145/3282431
Journal Article Type | Article |
---|---|
Acceptance Date | Sep 8, 2018 |
Online Publication Date | Nov 30, 2018 |
Publication Date | Nov 30, 2018 |
Deposit Date | Sep 10, 2018 |
Publicly Available Date | Sep 11, 2018 |
Journal | ACM Transactions on Computation Theory |
Print ISSN | 1942-3454 |
Electronic ISSN | 1942-3462 |
Publisher | Association for Computing Machinery (ACM) |
Peer Reviewed | Peer Reviewed |
Volume | 11 |
Issue | 1 |
Article Number | 3 |
DOI | https://doi.org/10.1145/3282431 |
Public URL | https://durham-repository.worktribe.com/output/1320642 |
Files
Accepted Journal Article
(911 Kb)
PDF
Copyright 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
You might also like
Computing balanced solutions for large international kidney exchange schemes
(2024)
Journal Article
An Algorithmic Framework for Locally Constrained Homomorphisms
(2024)
Journal Article
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
The Complexity of Matching Games: A Survey
(2023)
Journal Article
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
(2023)
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