ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems

Takehiro Ito, Jun Kawahara, Yu Nakahata, Takehide Soh, Akira Suzuki, Junichi Teruyama, Takahisa Toda

Given a graph $G$ and two independent sets $S, T$ of $G$, the independent set reconfiguration problem is the problem to determine whether $T$ can be obtained by repleatedly removing and adding a vertex from and to $S$, while intermediate sets must be also independent. This paper proposes an algorithm for the independent set reconfiguration problem using a data structure, called zero-suppressed binary decision diagrams (ZDDs). This algorithm can be generalized to various reconfiguration problems.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment