The Complexity of Bounded Length Graph Recoloring and CSP Reconfiguration

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 .