Coloring Reconfiguration Problems and Their Generalizations
弘基 大澤 · Institutional Repositories DataBase (IRDB) · 2020
Recently, the framework of reconfiguration problem is studied intensively in the field of theoretical computer science.The framework of reconfiguration deals with the problem where we wish to find a step-by-step transformation between initial and target configurations while preserving a constraint of some combinatorial search problem, and each step must respect a fixed reconfiguration rule.In this thesis we study a generalization of an well-studied reconfiguration problem k-coloring reconfiguration.In k-coloring reconfiguration, we are given two feasible k-colorings of a graph G, and asked to determine whether one coloring can be transformed into the other by recoloring one vertex at a time, while always maintaining a feasible k-coloring.In this thesis we generalize the reconfiguration rule of k-coloring reconfiguration by restricting recolorable pair of color, in the form of a (directed/undirected) graph whose vertex set is the color set {1, 2, . . ., k}, and give a precise analysis of the complexity status of the generalized problem with respect to the graph class of the graph whose vertices are colors. Directed recolorability5.1 NP-hardness for polytree . . . .