@inproceedings{674a207f5b654336a16d4ec41d8d52c2,

title = "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 .",

keywords = "Reconfiguration, EWI-25462, Coloring, METIS-309750, Graph algorithms, Constraint satisfaction, IR-93931, Computational Complexity",

author = "P.S. Bonsma and Mouawad, {Amer E.} and Naomi Nishimura and Venkatesh Raman",

note = "eemcs-eprint-25462 ; 9th International Symposium on Parameterized and Exact Computation, IPEC 2014 ; Conference date: 10-09-2014 Through 12-09-2014",

year = "2014",

month = sep,

doi = "10.1007/978-3-319-13524-3_10",

language = "English",

isbn = "978-3-319-13523-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "110--121",

editor = "Marek Cygan and Pinar Heggernes",

booktitle = "Proceedings of the 9th International Symposium on Parameterized and Exact Computation, IPEC 2014",

}