| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | September 5, 2017 |
| Latest Amendment Date: | April 6, 2021 |
| Award Number: | 1751765 |
| Award Instrument: | Standard Grant |
| Program Manager: |
A. Funda Ergun
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 15, 2017 |
| End Date: | March 31, 2022 (Estimated) |
| Total Intended Award Amount: | $141,056.00 |
| Total Awarded Amount to Date: | $141,056.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
200 N 7TH ST TERRE HAUTE IN US 47809-1902 (812)237-3088 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
IN US 47809-1902 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
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.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
The project studied the digraph homomorphism problem and its generalization. A homomorphism from digraph G to digraph H is a mapping from vertex set of G to vertex set of H that preserve the adjacency; the image of every arc of G is an arc of H under such a mapping. In the digraph homomorphism problem, HOM, digraph H is fixed, and the goal is to find a homomorphism from an input digraph G to H (aka. H-coloring). The digraph homomorphism problem is also equivalent to the constraint satisfaction problem. In the satisfaction problem, we have an input relational structure D and a target relational structure T, and the goal is to find a homomorphism from D to T.
In the optimization version of the HOM problem, known as the minimum cost homomorphism H (MinHOM(H)) the input digraph G is equipped with a cost function, where for every vertex u of G and every vertex $i$ of H, there is a cost of mapping u to i. In the MinHOM problem, the goal is to find a homomorphism from G to H with minimum total cost. The list homomorphism problem is a special case of the MinHOM problem where the costs are either zero or one, and the goal is to find a homomorphism from G to H with a total cost of zero. The structure of H plays a vital role in making these problems tractable. If target digraph H admits a particular symmetry, so-called polymorphism, then we hope to solve these problems in polynomial time or find an approximate solution in polynomial time. Semilattice, majority, and Maltsev polymorphisms are crucial in studies of homomorphism problems in digraphs.
One of the project's outputs is the characterizations of digraphs admitting conservative semilattice, also known as min orderable digraphs. Specifically, we have the following papers.
A) Min orderable digraphs (with Hell, Hunag, McConnell).
B) Bi-arc digraphs and conservative polymorphism (with Hell and Ak. Rafiey).
C) Recognizing interval bigraphs by forbidden patterns.
Another project output is the characterization and polynomial time recognition of the relational structure admitting Maltsev polymorphism. Specifically, we have the following paper.
D) Digraph Homomorphism problem with Maltsev condition (with Kinne and Murali).
Since many of the instances of the MinHOM(H) are NP-complete, we have studied the approximation of MinHOM(H). We have classified digraphs H for which MinHOM(H) can be approximated within a constant factor. Specifically, we have the following paper.
E) Towards a dichotomy for approximation of H-coloring (with Ak. Rafiey and Santos).
Finally, we have worked on a new notion, so-called sign list homomorphism, and found a dichotomy for the case of graphs. Specifically, we have the following paper.
F) Min ordering and list homomorphism dichotomies for signed and unsigned graphs (with Bok, Brewster, and Jedlikova).
Last Modified: 08/23/2022
Modified by: Arash Rafiey
Please report errors in award information by writing to: awardsearch@nsf.gov.
