Concise representation of hypergraph minimal transversals: Approach and application on the dependency inference problem
M. Nidhal Jelassi, Christine Largeron, Sadok Ben Yahia · 2015
The problem of extracting the minimal transversals from a hypergraph is known to be particularly difficult. Given that the number of minimal transversals can be exponential even for moderately sized hypergraphs, we propose, in this paper, a concise representation of minimal transversals in order to optimize the computation time and we introduce a new algorithm, called IRRED-ENGINE, which extracts all the minimal transversals from a subset. Experiments carried out on several types of hypergraphs, showed that IRRED-ENGINE obtains very interesting results evaluated through a compactness measure. To illustrate the benefit of our approach, we show how our concise representation can be used to solve the dependency inference problem by computing a concise cover of functional dependencies.