Efficient algorithms for dualizing large-scale hypergraphs

A hypergraph FF is a set family defined on vertex set VV. The dual of FF is the set of minimal subsets HH of VV such that F∩H≠0̸F∩H≠0̸ for any F∈FF∈F. The computation of the dual is equivalent to several problems, such as minimal hitting set enumeration of a subset family, generation problem for maximal frequent and minimal infrequent sets, and so on. Although many algorithms have been proposed for the problem, to the best of our knowledge, none of them can work on large-scale input with a large number of minimal hitting sets. In this paper, we propose efficient algorithms for checking the minimality and pruning methods. These algorithms enable us to construct time effective and polynomial space dualization algorithms. The computational experiments show that our algorithms are quite fast even for large-scale input for which existing algorithms do not terminate in a practical time.