Constraint Satisfaction Reconfiguration

The constraint satisfaction problem (CSP) is one of the classical problems studied in Theoretical Computer Science and asks for an assignment of values to variables such that given constraints are satisfied. The CSP includes as special cases for example graph coloring and Boolean satisfiability. Besides its theoretical importance, it has applications in many different domains, such as Scheduling, Operations Research, and Artificial Intelligence. We are interested in the structure of the solutions of CSP instances and approach this topic from the point-of-view of Combinatorial Reconfiguration. Based on our previous work, our goal is to make progress by pushing the limits of a recent topological approach to the problem.

Faculty Supervisor:

Richard Brewster

Student:

Partner:

Université Grenoble Alpes

Discipline:

Mathematics

Sector:

Education

University:

Thompson Rivers University

Program: