Dejan Delic, Ryerson University
“Homomorphism Dichotomy for Finite Oriented Trees”
The well-known CSP Dichotomy Conjecture, due to Feder and Vardi (1998) states that, for any finite relational template A, the homomorphism problem HOM(A) is either solvable in polynomial time or NP-complete. In the same article, it was proved that the conjecture can be reduced to an analogous one with the templates being restricted to the class of finite digraphs. For that reason, the investigation of the computational complexity of HOM(G), where G belongs to a particular class of digraphs, has gained a lot of interest in recent years. In particular, the Dichotomy Conjecture has been proved for the class of all undirected graphs, tournaments, digraphs without sources or sinks, special classes of oriented trees, etc.
In this talk, I will try to sketch a proof of the homomorphism dichotomy for the class of all finite oriented trees. The proof relies heavily on the construction given in a recent article by Bulin, Delic, Niven, and Jackson and the absorption theory in finite relational templates, due to Barto and Kozik.