Grant: Discovery Grants Program - Individual

The speed and power of modern computers is truly impressive. So much so, that one might believe any reasonable problem can be solved, even by brute force, in reasonable time. Surprisingly this is not the case. Consider the problem of assigning resources to a collection of users, for example scheduling teams in a round robin tournament. The goal is to assign the resources in the most efficient way possible, subject to constraints restricting the assignments. This a Constraint Satisfaction Problem or CSP. For a fast computer to exhaustively search through all the possible combinations looking for the optimum assignment could take thousands of years. This is an example of ""combinatorial explosion""; the sheer number of combinations defeats brute force solutions. More efficient algorithms, if they exist, must be employed. The primary aim of my program is to identify those CSPs which admit efficient algorithms (polynomial time solvable) and those which are intractable (NP-complete). Fundamentally we would like to know if such a dichotomy of efficient versus intractable holds for all CSPs. This would provide an understanding of the nature of these challenging combinatorial problems. Efficient algorithms are typically based on mathematical structure known as ""good characterizations"". A good characterization guides one through the combinatorial explosion to a solution for the CSP or to a proof that the CSP has no solution, i.e. there are too many constraints, at which point the search can stop. We seek to develop mathematical theory in the form of good characterizations for CSPs. The develop of this theory can be used to solve particular CSPs, but more importantly it gives insight into the fundamental dichotomy question above. My research program focuses on combinatorial problems from graph homomorphisms and digraph packings.