A reoccurring task in the design and profiling of relational data is the discovery of hidden dependencies between attributes.
Enumerating those dependencies is equivalent to the transversal hypergraph problem.
We devise a backtracking algorithm for the enumeration of inclusion-wise minimal hitting sets.
It achieves polynomial delay on hypergraphs for which the size of the largest minimal transversal is bounded. The algorithm solves the extension problem for minimal hitting sets as a subroutine. Although this problem is NP-complete and W-complete in general, we show that a careful implementation of the extension oracle can help avoiding the worst case on hypergraphs arising in the profiling of real-world databases, leading to significant speed-ups in practice.
This is joint work with Thomas Bläsius, Tobias Friedrich, Julius Lischeid, and Kitty Meeks.