A Parallel Approach to Counting Exact Covers Based on Decomposability Property

arXiv cs.AI / 4/17/2026

📰 NewsModels & Research

共有:

Key Points

The paper studies the NP-hard exact cover problem and focuses on counting all exact covers using knowledge-graph/knowledge-structure style representations.
It introduces decision-ZDNNF, a zero-suppressed variant of decision decomposable negation normal form, and shows it is strictly more succinct than existing ZBDD representations.
The authors develop a new parallel algorithm, DXD, that constructs a decision-ZDNNF representing the complete set of exact covers.
They further enhance DXD by dynamically updating connected components during execution.
Experiments indicate the improved DXD algorithm achieves better performance than all prior state-of-the-art methods for this task.

Abstract

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.