A Parallel Approach to Counting Exact Covers Based on Decomposability Property
For researchers and practitioners needing exact cover counting, this work provides a more efficient algorithm, though it is an incremental improvement over existing ZBDD-based methods.
The paper tackles the exact cover counting problem, an NP-hard problem with AI applications. The proposed DXD algorithm, based on a novel decision-ZDNNF representation, outperforms all state-of-the-art methods, achieving faster counting times.
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.