TY - GEN

T1 - Reconfiguration of colorable sets in classes of perfect graphs

AU - Ito, Takehiro

AU - Otachi, Yota

N1 - Funding Information:
Funding T.I. was partially supported by JST CREST Grant Number JPMJCR1402, and JSPS KAKENHI Grant Number JP16K00004, Japan. Y.O. was partially supported by MEXT KAK-ENHI Grant Number JP24106004, JSPS KAKENHI Grant Number JP25730003, and by FY 2015 Researcher Exchange Program between JSPS and NSERC.
Funding Information:
T.I. was partially supported by JST CREST Grant Number JPMJCR1402, and JSPS KAKENHI Grant Number JP16K00004, Japan. Y.O. was partially supported by MEXT KAKENHI Grant Number JP24106004, JSPS KAKENHI Grant Number JP25730003, and by FY 2015 Researcher Exchange Program between JSPS and NSERC.
Publisher Copyright:
© Takehiro Ito and Yota Otachi.

PY - 2018/6/1

Y1 - 2018/6/1

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 (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.

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 (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.

KW - Colorable set

KW - Perfect graph

KW - Phrases reconfiguration

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

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

U2 - 10.4230/LIPIcs.SWAT.2018.27

DO - 10.4230/LIPIcs.SWAT.2018.27

M3 - Conference contribution

AN - SCOPUS:85049053274

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 271

EP - 2713

BT - 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018

A2 - Eppstein, David

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 16th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2018

Y2 - 18 June 2018 through 20 June 2018

ER -