.png){kind=icon}
.png){kind=icon}
Return
Reconfiguring Multiple Connected Components with Size Multiset Constraints
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0218-9_6.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We propose a novel generalization of Independent Set Reconfiguration (ISR): Connected Components Reconfiguration (CCR). In CCR, we are given a graph G, two vertex subsets A and B, and a multiset M of positive integers. The question is whether A and B are reconfigurable under a certain rule, while ensuring that each vertex subset induces connected components whose sizes match the multiset M. ISR is a special case of CCR where M only contains 1. We also propose new reconfiguration rules: component jumping (CJ) and component sliding (CS), which regard connected components as tokens. Since CCR generalizes ISR, the problem is PSPACE-complete. In contrast, we show three positive results: First, CCR-CS and CCR-CJ are solvable in linear and quadratic time, respectively, when G is a path. Second, we show that CCR-CS is solvable in linear time for cographs. Third, when M contains only the same elements (i.e., all connected components have the same size), we show that CCR-CJ is solvable in linear time if G is chordal. The second and third results generalize known results for ISR and exhibit an interesting difference between the reconfiguration rules.
Keywords:
Combinatorial reconfiguration
Graph algorithm
Connected component
Cograph
Chordal graph
Journal
C
IF:
0
Papers:
24
Citations:
0