|
Constraint satisfaction problem (CSP) is a well-studied combinatorial problem, in which we are asked to find an assignment of values to given variables so as to satisfy all of given constraints. We study a reconfiguration variant of CSP, in which we are given an instance of CSP and two satisfying assignments, and asked to determine whether one assignment can be transformed into the other by changing a single variable assignment at a time, while always remaining satisfying assignment. This problem generalizes several well-studied reconfiguration problems such as Boolean satisfiability reconfiguration, vertex coloring reconfiguration, homomorphism reconfiguration. In this report, we study the problem from the viewpoints of polynomial-time solvability and parameterized complexity.
|
