AF: EAGER: Homomorphism Problems in Digraphs (Dichotomies)

图着色是理论计算机科学中最重要的问题之一。许多组合优化问题可以归结为图着色问题。对于给定的图G和整数k，问题是它的顶点是否存在k种颜色的着色，使得任何两个相邻的顶点得到不同的颜色。图(或有向图)同态问题是图着色问题的推广。在图同态问题中，目标是找到从输入图(或有向图)到固定目标图(或有向图)H的保持邻接关系的映射，同态问题及其等价形式被称为约束满足问题(CSP)，作为实际中必须解决的优化问题，有着广泛的应用。有向图同态问题和CSP问题是近二十年来理论计算机科学中非常活跃的两个研究领域。已经开发了几个工具(主要是代数)来解决CSP问题，最近出现了一些对该领域的主要猜想(称为CSP猜想)的解决方案(包括我们的解决方案)。本项目旨在详细验证每种方法，以提取最优雅的证明和最有效的算法。该方法是纯组合的，使用了图论的技术。该项目还将解决与CSP猜想的新提出的解决方案密切相关的问题。例如，PI为使同态问题可行的有向图H的类型寻求禁止的障碍刻画。这将有助于改善当前算法的运行时间。该项目还旨在通过培训理论计算机科学研究生、制作免费提供的高质量课堂讲稿和实地调查材料、在计算机领域寻找研究与其他重要研究领域之间的联系以及利用新的教学和传播方法，产生较高的教育影响。

Graph coloring is one of the most important problems in theoretical computer science. Many combinatorial optimization problems can be viewed as graph coloring problems. For a given graph G and integer k, the question is whether there exists a coloring of its vertices with k colors such that any two adjacent vertices receive different colors. The Graph (or Directed Graph) Homomorphism Problem is a generalization of graph coloring. In the Graph Homomorphism Problem, the goal is to find a mapping from an input graph (or digraph) to a fixed target graph (or digraph) H that preserves adjacency.Homomorphism problems, and the equivalent formulation as so-called constraint satisfaction problems (CSPs), enjoy a wide variety of applications as optimization problems that must be solved in practice. Such applications can be seen in scheduling, planning, databases, artificial intelligence, and many other areas.The Digraph Homomorphism Problem and CSPs have been two very active research areas in Theoretical Computer Science over the last two decades. Several tools (mostly algebraic) have been developed for solving CSPs, and very recently a number of proposed solutions (including our solution) to the main conjecture in the area (known as the CSP Conjecture) have arisen. The present project aims to verify in detail each approach to distill the most elegant proof and most efficient algorithms. The approach is purely combinatorial, using techniques from graph theory.The project will also tackle problems closely related to the newly proposed solutions to the CSP Conjecture. For example, the PIs seek forbidden obstruction characterizations for the types of digraphs H that make homomorphism problems feasible. This would help to improve the running time of the current algorithm.The project aims also to have a high educational impact, through training graduate students in theoretical computer science, producing freely available and high quality lecture notes and survey material on the field, seeking connections between the research and other important areas of research across computing, and utilizing novel teaching and dissemination methods.