Given a graph G and two independent sets of G, the independent set reconfiguration problem asks whether one independent set can be transformed into the other by moving a single vertex at a time, such that at each intermediate step we have an independent set of G. We study the complexity of this problem for H-free graphs under the token sliding and token jumping rule. Our contribution is twofold. First, we prove a reconfiguration analogue of Alekseev’s theorem for connected graphs H, showing that the problem is PSPACE-complete unless H is a path or a subdivision of the claw. We then show that under the token sliding rule the problem admits a polynomial-time algorithm if the input graph is fork-free, generalizing known results for \(P_4\) -free graphs and claw-free graphs. This implies a complete classification of the complexity of token sliding in H-free graphs, H being connected or not.

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

Independent Set Reconfiguration in H-Free Graphs

  • Valentin Bartier,
  • Nicolas Bousquet,
  • Moritz Mühlenthaler

摘要

Given a graph G and two independent sets of G, the independent set reconfiguration problem asks whether one independent set can be transformed into the other by moving a single vertex at a time, such that at each intermediate step we have an independent set of G. We study the complexity of this problem for H-free graphs under the token sliding and token jumping rule. Our contribution is twofold. First, we prove a reconfiguration analogue of Alekseev’s theorem for connected graphs H, showing that the problem is PSPACE-complete unless H is a path or a subdivision of the claw. We then show that under the token sliding rule the problem admits a polynomial-time algorithm if the input graph is fork-free, generalizing known results for \(P_4\) -free graphs and claw-free graphs. This implies a complete classification of the complexity of token sliding in H-free graphs, H being connected or not.