2026-07-23T04:52:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17289 2024-03-06T10:59:22Z ddc:004 open_access

Algorithms for Coloring Reconfiguration Under Recolorability Digraphs Fujii, Soichiro Iwamasa, Yuni Kimura, Kei Suzuki, Akira combinatorial reconfiguration graph coloring recolorability recoloring In the k-Recoloring problem, we are given two (vertex-)colorings of a graph using k colors, and asked to transform one into the other by recoloring only one vertex at a time, while at all times maintaining a proper k-coloring. This problem is known to be solvable in polynomial time if k ≤ 3, and is PSPACE-complete if k ≥ 4. In this paper, we consider a (directed) recolorability constraint on the k colors, which forbids some pairs of colors to be recolored directly. The recolorability constraint is given in terms of a digraph R, whose vertices correspond to the colors and whose arcs represent the pairs of colors that can be recolored directly. We provide algorithms for the problem based on the structure of recolorability constraints R, showing that the problem is solvable in linear time when R is a directed cycle or is in a class of multitrees. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Soichiro Fujii and Yuni Iwamasa and Kei Kimura and Akira Suzuki 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.4 urn:nbn:de:0030-drops-172896 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.4 eng https://creativecommons.org/licenses/by/4.0/legalcode