Reconfiguration of colorable sets in classes of perfect graphs
Reconfiguration of colorable sets in classes of perfect graphs
复制标题
完美图类中可着色集的重新配置
DOI：
10.1016/j.tcs.2018.11.024
复制
发表时间：
2019
影响因子：
1.1
通讯作者：
Otachi Yota
中科院分区：
文献类型：
--
作者：
Ito Takehiro;Otachi Yota
图中的一组顶点是可着色的，如果由该顶点集合引起的子图具有属性着色。在本文中，我们研究了在同一图的两个可色集之间寻找一个分步变换（称为重构序列）的问题。这个问题推广了研究得很好的独立集重构问题。作为系统地理解这个一般问题的复杂性的第一步，我们研究了关于完美图类的问题。我们首先关注区间图，并给出了两个可色集之间距离的组合表征。这给出了一种线性时间算法，用于寻找间隔图的实际最短重构序列。由于区间图正是同时具有弦性和共可比性的图，因此我们通过证明即使决定可达性对于弦性图和共可比性图也是pspace完全的来补充肯定的结果。弦图的硬度甚至对分割图也成立。我们还考虑了一个固定常数的情况，并证明在这种情况下，可达性问题对于分裂图是多项式时间可解的，但对于共可比性图仍然是pspace完全的。弦图的这种情况的复杂性仍未解决。作为副产品，我们的积极结果给出了反馈顶点集重构的第一个多项式时间可解情况（分裂图和间隔图）。
A set of vertices in a graph isc-colorableif the subgraph induced by the set has a properc-coloring. In this paper, we study the problem of finding a step-by-step transformation (called a reconfiguration sequence) between twoc-colorable sets in the same graph. This problem generalizes the well-studiedIndependent Set Reconfigurationproblem. 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 twoc-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 wherecis 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) forFeedback Vertex Set Reconfiguration.