AF: EAGER: Homomorphism Problems in Digraphs (Dichotomies)

Indiana State University, Terre Haute IN

Investigators

Abstract

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.