Dichotomy for Digraph Homomorphism Problems

Abstract

We consider the problem of finding a homomorphism from an input digraph $G$ to a fixed digraph $H$. We show that if $H$ admits a weak-near-unanimity polymorphism $\varphi$ then deciding whether $G$ admits a homomorphism to $H$ (HOM($H$)) is polynomial time solvable? This gives a proof of the dichotomy conjecture (now dichotomy theorem) by Feder and Vardi [29]. Our approach is combinatorial, and it is simpler than the two algorithms found by Bulatov [9] and Zhuk [46] in 2017. We have implemented our algorithm and show some experimental results.

References in corpus (1)

• Refuting Feder, Kinne and Rafiey

Cited by in corpus (8)

• Dichotomies in Ontology-Mediated Querying with the Guarded Fragment
• The complexity of tropical graph homomorphisms
• Time Complexity of Constraint Satisfaction via Universal Algebra
• Graph Homomorphism Reconfiguration and Frozen $H$-Colourings
• Refuting Feder, Kinne and Rafiey
• Digraphs Homomorphism Problems with Maltsev Condition
• Digraph homomorphism problem and weak near unanimity polymorphism
• Kernelization of Constraint Satisfaction Problems: A Study through Universal Algebra