Surjective H-Colouring over Reflexive Digraphs

作     者：Larose, Benoit Martin, Barnaby Paulusma, Daniel 

作者机构：Univ Quebec Montreal LACIM CP 8888Succursale Ctr Ville Montreal PQ H3C 3P8 Canada Univ Durham Dept Comp Sci Durham England 

出 版 物：《ACM TRANSACTIONS ON COMPUTATION THEORY》 (美国计算机学会计算理论汇刊)

年 卷 期：2019年第11卷第1期

页      面：3-3页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSERC FRQNT Leverhulme Trust [RPG-2016-258] 

主　　题：Surjective H-Coloring computational complexity algorithmic graph theory universal algebra constraint satisfaction 

摘      要：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.