# A Parallel Approach to Counting Exact Covers Based on Decomposability Property

arXiv: https://arxiv.org/abs/2604.14627 · HTML: https://mlsanity.com/paper/2604.14627/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 31 references that are in the map.
- First posted on arXiv 16 Apr 2026.

## Builds on (most cited first, 1 of 1)

- [Model Counting of Query Expressions: Limitations of Propositional Methods](https://mlsanity.com/paper/1312.4125/) (2013)

## Abstract (arXiv)

The exact cover problem is a classical NP-hard problem with broad applications in the area of AI. Algorithm DXZ is a method to count exact covers representing by zero-suppressed binary decision diagrams (ZBDDs). In this paper, we propose a zero-suppressed variant of decision decomposable negation normal form (in short, decision-ZDNNF), which is strictly more succinct than ZBDDs. We then design a novel parallel algorithm, namely DXD, which constructs a decision-ZDNNF representing the set of all exact covers. Furthermore, we improve DXD by dynamically updating connected components. The experimental results demonstrate that the improved DXD algorithm outperforms all of state-of-the-art methods.