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 \(\mathcal {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 \(\mathcal {M}\) . ISR is a special case of CCR where \(\mathcal {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 \(\mathcal {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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Reconfiguring Multiple Connected Components with Size Multiset Constraints

  • Yu Nakahata

摘要

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 \(\mathcal {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 \(\mathcal {M}\) . ISR is a special case of CCR where \(\mathcal {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 \(\mathcal {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.