The complexity of bounded length graph recoloring and CSP reconfiguration

Abstract. In the first part of this work we study the following question: Given two k-colorings α and β of a graph G on n vertices and an integer `, can α be modified into β by recoloring vertices one at a time, while maintaining a k-coloring throughout and using at most ` such recoloring steps? This problem is weakly PSPACE-hard for every constant k ≥ 4. We show that the problem is also strongly NP-hard for every constant k ≥ 4 and W[1]-hard (but in XP) when parameterized only by `. On the positive side, we show that the problem is fixed-parameter tractable when parameterized by k+ `. In fact, we show that the more general problem of `-length bounded reconfiguration of constraint satisfaction problems (CSPs) is fixed-parameter tractable parameterized by k + ` + r, where r is the maximum constraint arity and k is the maximum domain size. We show that for parameter `, the latter problem is W[2]-hard, even for k = 2. Finally, if p denotes the number of variables with different values in the two given assignments, we show that the problem is W[2]-hard when parameterized by ` − p, even for k = 2 and r = 3.