This paper proposes an algorithmic framework for various reconfiguration problems using zero-suppressed binary decision diagrams (ZDDs), a data structure for families of sets. In general, a reconfiguration problem checks if there is a step-by-step transformation between two given feasible solutions (e.g., independent sets of an input graph) of a fixed search problem such that all intermediate results are also feasible and each step obeys a fixed reconfiguration rule (e.g., adding/removing a single vertex to/from an independent set). The solution space formed by all feasible solutions can be exponential in the input size, and indeed many reconfiguration problems are known to be PSPACE-complete. This paper shows that an algorithm in the proposed framework efficiently conducts the breadth-first search by compressing the solution space using ZDDs, and finds a shortest transformation between two given feasible solutions if exists. Moreover, the proposed framework provides rich information on the solution space, such as the connectivity of the solution space and all feasible solutions reachable from a specified one. We demonstrate that the proposed framework can be applied to various reconfiguration problems, and experimentally evaluate their performances.

翻译：本文建议了使用零压二进制决定图(ZDDs)解决各种重组问题的算法框架,这是各组家庭的数据结构。一般而言,如果在固定搜索问题的两个给定可行解决方案(如独立输入图集)之间发生逐步转换(如独立输入图集),则重组问题检查,这样所有中间结果也是可行的,而且每个步骤都遵守固定重组规则(例如,在独立数据集之间增加/移动单一的顶点)。所有可行的解决方案所形成的解决方案空间在输入大小上可以成倍增长,而且许多重组问题确实众所周知是PSPACE的完整。该文件表明,拟议框架中的算法通过使用ZDDs压缩解决方案空间,有效地进行了宽度第一搜索,并在存在两个给定的可行解决方案时发现最短的转换。此外,拟议框架提供了有关解决方案空间的丰富信息,例如解决方案空间的连接性以及从一个指定的解决方案可以达到的所有可行解决方案。我们证明拟议的框架可以应用于各种重组问题,并实验性地评估其性能。