The Complexity of Bounded Length Graph Recoloring

2014/04/01 by Paul Bonsma, Bonsma, Paul, Amer E. Mouawad +1
Computer Science · #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS

paper · pdf · doi:10.48550/arxiv.1404.0337

arxiv created 2014/04/16 · arxiv updated 2014/04/17

Abstract

We study the following question: Given are two k-colorings α and β of a graph G on n vertices, and integer ℓ. The question is whether α 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 it is also strongly NP-hard for every constant k≥ 4. On the positive side, we give an O(f(k,ℓ) n^O(1)) algorithm for the problem, for some computable function f. Hence the problem is fixed-parameter tractable when parameterized by k+ℓ. Finally, we show that the problem is W[1]-hard (but in XP) when parameterized only by ℓ.

Related

• Finding Shortest Paths between Graph Colourings
• Sharp Bounds on Lengths of Linear Recolouring Sequences
• Fixing improper colorings of graphs
• The Complexity of (List) Edge-Coloring Reconfiguration Problem
• A Note on the Complexity of Graph Recoloring