TY - JOUR

T1 - Reconfiguration of colorable sets in classes of perfect graphs

AU - Ito, Takehiro

AU - Otachi, Yota

N1 - Funding Information:
T.I. was partially supported by JST CREST Grant Number JPMJCR1402, and JSPS KAKENHI Grant Numbers JP16K00004 and JP18H04091, Japan.Y.O. was partially supported by MEXT KAKENHI Grant Number JP24106004, JSPS KAKENHI Grant Numbers JP25730003, JP18K11168, JP18K11169, JP18H04091, and by FY 2015 Researcher Exchange Program between JSPS and NSERC. The authors thank Benjamin R. Moore for asking a question on structural parameterizations of the problem, which led to the final remark in Section 7. The authors are grateful to the anonymous reviewers for their constructive comments.
Funding Information:
Y.O. was partially supported by MEXT KAKENHI Grant Number JP24106004, JSPS KAKENHI Grant Numbers JP25730003, JP18K11168, JP18K11169, JP18H04091, and by FY 2015 Researcher Exchange Program between JSPS and NSERC.
Publisher Copyright:
© 2018 Elsevier B.V.

PY - 2019/6/7

Y1 - 2019/6/7

N2 - 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 (called a reconfiguration sequence) 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.

AB - 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 (called a reconfiguration sequence) 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.

KW - Colorable set

KW - Combinatorial reconfiguration

KW - Graph algorithm

KW - Perfect graph

UR - http://www.scopus.com/inward/record.url?scp=85057536164&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85057536164&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2018.11.024

DO - 10.1016/j.tcs.2018.11.024

M3 - Article

AN - SCOPUS:85057536164

VL - 772

SP - 111

EP - 122

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -