Number of Minimal Hypergraph Transversals and Complexity of IFM with Infrequency: High in Theory, but Often Not so Much in Practice!

摘要

Hypergraph Dualization (also called as hitting set enumeration) is the problem of enumerating all minimal transversals of a hypergraph H, i.e., all minimal inclusion-wise hyperedges (i.e., sets of vertices) that intersect every hyperedge in H. Dualization is at the core of many important Artificial Intelligence (AI) problems. As a contribution to a better understanding of Dualization complexity, this paper introduces a tight upper bound to the number of minimal transversals that can be computed in polynomial time. In addition, the paper presents an interesting exploitation of the upper bound to the number of minimal transversals. In particular, the problem dealt with is characterizing the complexity of the data mining problem called IFM_I (Inverse Frequent itemset Mining with Infrequency constraints), that is the problem of finding a transaction database whose frequent and infrequent itemsets satisfy a number of frequency/infrequency patterns given in input.