Compressing Exact Cover Problems with Zero-suppressed Binary Decision Diagrams
Masaaki Nishino, Norihito Yasuda, Kengo Nakamura
Abstract
Exact cover refers to the problem of finding subfamily F of a given family of sets S whose universe is D, where F forms a partition of D. Knuth’s Algorithm DLX is a state-of-the-art method for solving exact cover problems. Since DLX’s running time depends on the cardinality of input S, it can be slow if S is large. Our proposal can improve DLX by exploiting a novel data structure, DanceDD, which extends the zero-suppressed binary decision diagram (ZDD) by adding links to enable efficient modifications of the data structure. With DanceDD, we can represent S in a compressed way and perform search in linear time with the size of the structure by using link operations. The experimental results show that our method is an order of magnitude faster when the problem is highly compressed.
BibTeX
@inproceedings{ijcai2021p275,
title = {Compressing Exact Cover Problems with Zero-suppressed Binary Decision Diagrams},
author = {Nishino, Masaaki and Yasuda, Norihito and Nakamura, Kengo},
booktitle = {Proceedings of the Thirtieth International Joint Conference on
Artificial Intelligence, {IJCAI-21}},
publisher = {International Joint Conferences on Artificial Intelligence Organization},
editor = {Zhi-Hua Zhou},
pages = {1996--2004},
year = {2021},
month = {8},
note = {Main Track},
doi = {10.24963/ijcai.2021/275},
url = {https://doi.org/10.24963/ijcai.2021/275},
}