  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.
