咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Reconfiguration of colorable s... 收藏

Reconfiguration of colorable sets in classes of perfect graphs

在完美的图的班上的可着色的集合的重构

作     者:Ito, Takehiro Otachi, Yota 

作者机构:Tohoku Univ Grad Sch Informat Sci Aoba Yama 6-6-05 Sendai Miyagi 9808579 Japan Kumamoto Univ Fac Adv Sci & Technol Chuo Ku 2-39-1 Kurokami Kumamoto 8608555 Japan 

出 版 物:《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期:2019年第772卷

页      面:111-122页

核心收录:

学科分类:08[工学] 0812[工学-计算机科学与技术(可授工学、理学学位)] 

基  金:JST CREST [JPMJCR1402] JSPS KAKENHI, Japan [JP16K00004, JP18H04091] MEXT KAKENHI [JP24106004] JSPS KAKENHI [JP18H04091, JP25730003, JP18K11168, JP18K11169] JSPS NSERC 

主  题:Combinatorial reconfiguration Graph algorithm Colorable set Perfect graph 

摘      要: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. (C) 2018 Elsevier B.V. All rights reserved.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分