A Scalable Scheme for Counting Linear Extensions

A Scalable Scheme for Counting Linear Extensions

Topi Talvitie, Kustaa Kangas, Teppo Niinimäki, Mikko Koivisto

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 5119-5125. https://doi.org/10.24963/ijcai.2018/710

Counting the linear extensions of a given partial order not only has several applications in artificial intelligence but also represents a hard problem that challenges modern paradigms for approximate counting. Recently, Talvitie et al. (AAAI 2018) showed that an exponential time scheme beats the fastest known polynomial time schemes in practice, even if allowing hours of running time. Here, we present a novel scheme, relaxation Tootsie Pop, which in our experiments exhibits polynomial characteristics and significantly outperforms previous schemes. We also instantiate state-of-the-art model counters for CNF formulas; two natural encodings yield schemes that, however, are inferior to the more specialized schemes.
Keywords:
Uncertainty in AI: Approximate Probabilistic Inference
Uncertainty in AI: Bayesian Networks
Heuristic Search and Game Playing: Combinatorial Search and Optimisation
Constraints and SAT: SAT: Applications