Algorithms for coloring reconfiguration under recolorability digraphs

Soichiro Fujii*, Yuni Iwamasa, Kei Kimura, Akira Suzuki

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

12 Downloads (Pure)

Abstract

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.

Original languageEnglish
Title of host publicationISAAC 2022
Subtitle of host publication33rd International Symposium on Algorithms and Computation
EditorsSang Won Bae, Heejin Park
Place of PublicationWadern
PublisherDagstuhl Publishing
Pages4:1–4:19
Number of pages19
ISBN (Electronic)9783959772587
DOIs
Publication statusPublished - 1 Dec 2022
Event33rd International Symposium on Algorithms and Computation, ISAAC 2022 - Virtual, Online, Korea, Republic of
Duration: 19 Dec 202221 Dec 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume248
ISSN (Print)1868-8969

Conference

Conference33rd International Symposium on Algorithms and Computation, ISAAC 2022
Country/TerritoryKorea, Republic of
CityVirtual, Online
Period19/12/2221/12/22

Bibliographical note

Copyright © Soichiro Fujii, Yuni Iwamasa, Kei Kimura, and Akira Suzuki. Version archived for private and non-commercial use with the permission of the author/s and according to publisher conditions. For further rights please contact the publisher.

Keywords

  • combinatorial reconfiguration
  • graph coloring
  • recolorability
  • recoloring

Fingerprint

Dive into the research topics of 'Algorithms for coloring reconfiguration under recolorability digraphs'. Together they form a unique fingerprint.

Cite this