In a reconfiguration problem, we are given two feasible solutions of a combinatorial problem and our goal is to determine whether it is possible to reconfigure one into the other, with the steps dictated by specific reconfiguration rules. Traditionally, most studies on reconfiguration problems have focused on rules that allow changing a single element at a time. In contrast, this paper considers scenarios in which \(k \ge 2\) elements can be changed simultaneously. We investigate the general reconfiguration problem of isomorphisms. For the Induced Subgraph Isomorphism Reconfiguration problem, we show that the problem remains PSPACE-complete even under stringent constraints on the pattern graph when k is constant. We then give two meta-theorems applicable when k is slightly less than the number of vertices in the pattern graph. In addition, we investigate the complexity of the Independent Set Reconfiguration problem, which is a special case of the Induced Subgraph Isomorphism Reconfiguration problem.

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

Changing Induced Subgraph Isomorphisms Under Extended Reconfiguration Rules

  • Tatsuhiro Suga,
  • Akira Suzuki,
  • Yuma Tamura,
  • Xiao Zhou

摘要

In a reconfiguration problem, we are given two feasible solutions of a combinatorial problem and our goal is to determine whether it is possible to reconfigure one into the other, with the steps dictated by specific reconfiguration rules. Traditionally, most studies on reconfiguration problems have focused on rules that allow changing a single element at a time. In contrast, this paper considers scenarios in which \(k \ge 2\) elements can be changed simultaneously. We investigate the general reconfiguration problem of isomorphisms. For the Induced Subgraph Isomorphism Reconfiguration problem, we show that the problem remains PSPACE-complete even under stringent constraints on the pattern graph when k is constant. We then give two meta-theorems applicable when k is slightly less than the number of vertices in the pattern graph. In addition, we investigate the complexity of the Independent Set Reconfiguration problem, which is a special case of the Induced Subgraph Isomorphism Reconfiguration problem.