License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SWAT.2018.27
URN: urn:nbn:de:0030-drops-88539
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8853/
Go to the corresponding LIPIcs Volume Portal

Ito, Takehiro ; Otachi, Yota

Reconfiguration of Colorable Sets in Classes of Perfect Graphs

pdf-format:
LIPIcs-SWAT-2018-27.pdf (0.5 MB)

Abstract

A set of vertices in a graph is c-colorable if the subgraph induced by the set has a proper c-coloring. In this paper, we study the problem of finding a step-by-step transformation (reconfiguration) between two c-colorable sets in the same graph. This problem generalizes the well-studied Independent Set Reconfiguration problem. As the first step toward a systematic understanding of the complexity of this general problem, we study the problem on classes of perfect graphs. We first focus on interval graphs and give a combinatorial characterization of the distance between two c-colorable sets. This gives a linear-time algorithm for finding an actual shortest reconfiguration sequence for interval graphs. Since interval graphs are exactly the graphs that are simultaneously chordal and co-comparability, we then complement the positive result by showing that even deciding reachability is PSPACE-complete for chordal graphs and for co-comparability graphs. The hardness for chordal graphs holds even for split graphs. We also consider the case where c is a fixed constant and show that in such a case the reachability problem is polynomial-time solvable for split graphs but still PSPACE-complete for co-comparability graphs. The complexity of this case for chordal graphs remains unsettled. As by-products, our positive results give the first polynomial-time solvable cases (split graphs and interval graphs) for Feedback Vertex Set Reconfiguration.

BibTeX - Entry

@InProceedings{ito_et_al:LIPIcs:2018:8853,
  author =	{Takehiro Ito and Yota Otachi},
  title =	{{Reconfiguration of Colorable Sets in Classes of Perfect Graphs}},
  booktitle =	{16th Scandinavian Symposium and Workshops on Algorithm  Theory (SWAT 2018)},
  pages =	{27:1--27:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-068-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{101},
  editor =	{David Eppstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8853},
  URN =		{urn:nbn:de:0030-drops-88539},
  doi =		{10.4230/LIPIcs.SWAT.2018.27},
  annote =	{Keywords: reconfiguration, colorable set, perfect graph}
}

Keywords: reconfiguration, colorable set, perfect graph
Collection: 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Issue Date: 2018
Date of publication: 04.06.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI