权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

AF: EAGER: Homomorphism Problems in Digraphs (Dichotomies)

AF：EAGER：有向图中的同态问题（二分法）

基本信息

批准号：
1751765
负责人：
Arash Rafiey
金额：
$ 14.11万
依托单位：
Indiana State University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-09-15 至 2022-03-31
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1751765&HistoricalAwards=false
关键词：
AF EAGER Homomorphism Problems Digraphs

项目摘要

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.

图的着色是理论计算机科学中最重要的问题之一。许多组合优化问题都可以看作是图着色问题。对于给定的图G和整数k，问题是是否存在用k种颜色对其顶点着色，使得任意两个相邻顶点得到不同的颜色。图（或有向图）同态问题是图着色问题的一个推广。在图同态问题中，目标是找到从输入图（或有向图）到保持邻接性的固定目标图（或有向图）H的映射。同态问题，以及所谓的约束满足问题（csp）的等价公式，作为在实践中必须解决的优化问题，有着广泛的应用。这样的应用可以在调度、计划、数据库、人工智能和许多其他领域看到。在过去的二十年里，有向图同态问题和csp是理论计算机科学中两个非常活跃的研究领域。已经开发了一些工具（主要是代数工具）来求解CSP，并且最近出现了许多针对该领域主要猜想（称为CSP猜想）的建议解决方案（包括我们的解决方案）。本项目旨在详细验证每种方法，以提取最优雅的证明和最有效的算法。该方法是纯组合的，使用图论的技术。该项目还将解决与CSP猜想新提出的解决方案密切相关的问题。例如，pi寻求使同态问题可行的有向图H类型的禁阻表征。这将有助于改善当前算法的运行时间。该项目还旨在通过培养理论计算机科学的研究生，制作免费和高质量的课堂讲稿和实地调查材料，寻求研究与其他重要计算研究领域之间的联系，以及利用新颖的教学和传播方法，产生高教育影响。