Enumeration of Minimal Hitting Sets on Bounded Treewidth Hypergraphs: From Theory to Practice

Abstract: The enumeration of minimal hitting sets in hypergraphs is a challenging problem with applications across various domains. We present a new algorithm that leverages hypergraph treewidth to achieve fixed-parameter linear delay, significantly improving existing approaches. Our implementation, released as a Python library, features a novel data structure and algorithms for enumerating minimal hitting sets and minimal dominating sets. Additionally, it allows users to impose constraints on the output, such as required or excluded nodes, making it a versatile tool for both theoretical and practical applications.