2024/02/20 by Banerjee, Niranka, Engels, Christian, Hoang, Duc A.
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2402.12705
For integers d ≥ 1 and k ≥ d+1, the Distance Coloring problem asks if a given graph G has a (d, k)-coloring, i.e., a coloring of the vertices of G by k colors such that any two vertices within distance d from each other have different colors. In particular, the well-known Coloring problem is a special case of Distance Coloring when d = 1. For integers d ≥ 2 and k ≥ d+1, the (d, k)-Coloring Reconfiguration problem asks if there is a way to change the color of one vertex at a time, starting from a (d, k)-coloring α of a graph G to reach another (d, k)-coloring β of G, such that all intermediate colorings are also (d, k)-colorings. We show that even for planar, bipartite, and 2-degenerate graphs, (d, k)-Coloring Reconfiguration remains PSPACE-complete for d ≥ 2 and k = Ω(d2) via a reduction from the well-known Sliding Tokens problem. Additionally, on split graphs, there is an interesting dichotomy: the problem is PSPACE-complete when d = 2 and k is large but can be solved efficiently when d ≥ 3 and k ≥ d+1. For chordal graphs, we show that the problem is PSPACE-complete for even values of d ≥ 2. Finally, we design a quadratic-time algorithm to solve the problem on paths for any d ≥ 2 and k ≥ d+1.