Larose, Benoit ;
Martin, Barnaby ;
Paulusma, Daniel
Surjective HColouring over Reflexive Digraphs
Abstract
The Surjective HColouring problem is to test if a given graph allows a vertexsurjective homomorphism to a fixed graph H. The complexity of this problem has been well studied for undirected (partially) reflexive graphs. We introduce endotriviality, 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 complexitytheoretic classifications of Surjective HColouring in the case of reflexive digraphs.
Chen [2014] proved, in the setting of constraint satisfaction problems, that Surjective HColouring is NPcomplete 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 endotrivial reflexive digraph H has this property. We then use the concept of endotriviality to prove, as our main result, a dichotomy for Surjective HColouring when H is a reflexive tournament: if H is transitive, then Surjective HColouring is in NL, otherwise it is NPcomplete.
By combining this result with some known and new results we obtain a complexity classification for Surjective HColouring when H is a partially reflexive digraph of size at most 3.
BibTeX  Entry
@InProceedings{larose_et_al:LIPIcs:2018:8488,
author = {Benoit Larose and Barnaby Martin and Daniel Paulusma},
title = {{Surjective HColouring over Reflexive Digraphs}},
booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
pages = {49:149:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770620},
ISSN = {18688969},
year = {2018},
volume = {96},
editor = {Rolf Niedermeier and Brigitte Vall{\'e}e},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8488},
URN = {urn:nbn:de:0030drops84882},
doi = {10.4230/LIPIcs.STACS.2018.49},
annote = {Keywords: Surjective HColoring, Computational Complexity, Algorithmic Graph Theory, Universal Algebra, Constraint Satisfaction}
}
27.02.2018
Keywords: 

Surjective HColoring, Computational Complexity, Algorithmic Graph Theory, Universal Algebra, Constraint Satisfaction 
Seminar: 

35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Issue date: 

2018 
Date of publication: 

27.02.2018 