  Constraint satisfaction problem (CSP) is a well-studied combinatorial search
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 together with its 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 paper, we study the problem from the viewpoints of polynomial-time
solvability and parameterized complexity, and give several interesting
boundaries of tractable and intractable cases.
