Surjective H-Colouring over Reflexive Digraphs

DOI10.1145/3282431zbMATH Open1485.68190arXiv1709.09486OpenAlexW2963569011WikidataQ130952119 ScholiaQ130952119MaRDI QIDQ5205804FDOQ5205804

Authors: Benoît Larose, Barnaby Martin, Daniël Paulusma 

Publication date: 16 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1709.09486

Recommendations

• Surjective \texttt{H}-colouring over reflexive digraphs
• Surjective \(H\)-colouring: new hardness results
• Surjective \(H\)-colouring: new hardness results
• scientific article; zbMATH DE number 2156263
• Injective colouring for H-free graphs
• \(H\)-coloring dichotomy revisited
• \(H\)-coloring degree-bounded (acyclic) digraphs
• Coloring \(H\)-free hypergraphs
• -panchromatic digraphs
• scientific article; zbMATH DE number 2080268

zbMATH Keywords

computational complexityconstraint satisfactionuniversal algebraalgorithmic graph theorysurjective H-coloring

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Applications of universal algebra in computer science (08A70)

Cited In (4)

• Surjective \texttt{H}-colouring over reflexive digraphs
• Algebraic global gadgetry for surjective constraint satisfaction
• Surjective polymorphisms of directed reflexive cycles
• A reflexive digraph that is retraction trivial but not endomorphism trivial

This page was built for publication: Surjective H-Colouring over Reflexive Digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5205804)