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.
展开▼
