View article

This paper proposes an algorithmic framework for solving various combinatorial reconfiguration problems by using zero-suppressed binary decision diagrams (ZDDs), a data structure for representing 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 breadth-first search by compressing the solution space using ZDDs, and that it finds a shortest …